fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define mp make_pair
  7. //#define int long long
  8. #define sz(x) (int)(x).size()
  9. #define all(x) (x).begin(), (x).end()
  10. #define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
  11. #define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)
  12.  
  13. typedef long long ll;
  14. typedef pair<int, int> pii;
  15. typedef pair<ll, ll> pll;
  16.  
  17. template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
  18. template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }
  19.  
  20. const int siz = 2e3 + 2;
  21. const int SIZ = 1e6 + 2;
  22. const int mod = 1e9 + 7;
  23. const int maxx = 2e9;
  24. const ll MAXX = 1e18;
  25. const string file = "paint";
  26.  
  27. int n, a, b;
  28. int p[siz];
  29.  
  30. bool check(int w) {
  31.     int cnt = 0;
  32.     rep (i, 1, n) {
  33.         cnt++;
  34.         int j = i;
  35.  
  36.         while (j < n && p[j + 1] - p[i] + 1 <= w) {
  37.             /// p[j]  được tô
  38.             j++;
  39.         }
  40.         /// cây cọ p[i] -> p[i] + w - 1
  41.  
  42.         /// do đó p[j] <= (p[i] + w - 1) sẽ được tô
  43.  
  44.         /// p[j] - p[i] + 1 <= w
  45.  
  46.         i = j;
  47.     }
  48.  
  49.     return cnt <= a;
  50. }
  51.  
  52. signed main() {
  53.     ios::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  55.  
  56.     if (fopen((file + ".inp").c_str(), "r")) {
  57.         freopen((file + ".inp").c_str(), "r", stdin);
  58.         freopen((file + ".out").c_str(), "w", stdout);
  59.     }
  60.  
  61.     cin >> n >> a >> b;
  62.  
  63.     rep (i, 1, n) {
  64.         cin >> p[i];
  65.     }
  66.  
  67.     if (a + b >= n) {
  68.         cout << 1 << "\n";
  69.         return 0;
  70.     }
  71.  
  72.     /// các ô đặc biệt sẽ tăng dần
  73.  
  74.     sort(p + 1, p + n + 1);
  75.  
  76.     /// p[1] -> p[1] + w - 1
  77.  
  78.     int ans = -1;
  79.     for (int lb = 1, rb = 1e9; lb <= rb; ) {
  80.         int mb = (lb + rb) / 2;
  81.  
  82.         if (check(mb)) {
  83.             ans = mb;
  84.             rb = mb - 1;
  85.         } else {
  86.             lb = mb + 1;
  87.         }
  88.     }
  89.  
  90.     cout << ans << "\n";
  91.  
  92. //    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
  93.  
  94.     return 0;
  95. }
  96.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/aVTgen
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!