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