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. int dp[siz][siz];
  30.  
  31. bool check(int w) {
  32.     memset(dp, 0x3f, sizeof(dp));
  33.     dp[0][0] = 0;
  34.     rep (i, 1, n) {
  35.         int j_1 = lower_bound(p + 1, p + n + 1, p[i] - w + 1) - p - 1;
  36.  
  37.         int j_2 = lower_bound(p + 1, p + n + 1, p[i] - 2 * w + 1) - p - 1;
  38.  
  39.         rep (k, 0, a) {
  40.             if (k > 0) {
  41.                 minimize(dp[i][k], dp[j_1][k - 1]);
  42.             }
  43.             minimize(dp[i][k], dp[j_2][k] + 1);
  44.         }
  45.     }
  46.  
  47.     rep (k, 0, a) {
  48.         /// dp[n][k] = y
  49.         /// dp[p1, p2, ..., pn][ k cái cọ w]  = true và y  cái cọ w * 2
  50.         if (dp[n][k] <= b) {
  51.             return true;
  52.         }
  53.     }
  54.  
  55.     return false;
  56. }
  57.  
  58. signed main() {
  59.     ios::sync_with_stdio(false);
  60.     cin.tie(nullptr);
  61.  
  62.     if (fopen((file + ".inp").c_str(), "r")) {
  63.         freopen((file + ".inp").c_str(), "r", stdin);
  64.         freopen((file + ".out").c_str(), "w", stdout);
  65.     }
  66.  
  67.     cin >> n >> a >> b;
  68.  
  69.     rep (i, 1, n) {
  70.         cin >> p[i];
  71.     }
  72.  
  73.     if (a + b >= n) {
  74.         cout << 1 << "\n";
  75.         return 0;
  76.     }
  77.  
  78.     sort(p + 1, p + n + 1);
  79.  
  80.     int ans = -1;
  81.     for (int lb = 1, rb = 1e9; lb <= rb; ) {
  82.         int mb = (lb + rb) / 2;
  83.  
  84.         if (check(mb)) {
  85.             ans = mb;
  86.             rb = mb - 1;
  87.         } else {
  88.             lb = mb + 1;
  89.         }
  90.     }
  91.  
  92.     cout << ans << "\n";
  93.  
  94. //    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
  95.  
  96.     return 0;
  97. }
  98.  
  99.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/IhP8QD
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!