fork download
copy 
  1. // https://o...content-available-to-author-only...i.info/problem/fct017_giangseq
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define IO(NAME) \
  6.     cin.tie(0)->sync_with_stdio(false); \
  7.     if (fopen(NAME ".inp", "r")) { \
  8.         freopen(NAME ".inp", "r", stdin); \
  9.         freopen(NAME ".out", "w", stdout); \
  10.     };
  11. #define int long long 
  12. #define main() signed main()
  13. #define x first 
  14. #define y second 
  15. #define pb push_back 
  16. #define mp make_pair 
  17. #define sqr(x) (x) * (x)
  18. #define all(a) a.begin(), a.end()
  19. typedef vector<int> vt;
  20. typedef pair<int, int> ii;
  21. typedef vector<ii> vii;
  22.  
  23. const int N = 2e3 + 7, inf = 1e18;
  24. int n, k, a[N];
  25. ii dp[N];
  26.  
  27. bool check(int mid) {
  28.     int tmp = 0;
  29.     for (int i = 1; i <= n; i++) {
  30.         tmp += mid;
  31.         dp[i] = mp(tmp - a[i], tmp + a[i]);
  32.     }
  33.     sort (dp + 1, dp + 1 + n);
  34.     vt v;
  35.     v.pb(dp[1].y);
  36.     for (int i = 2; i <= n; i++) {
  37.         if (v.back() <= dp[i].y) v.pb(dp[i].y);
  38.         else *upper_bound(all(v), dp[i].y) = dp[i].y;
  39.     }
  40.     return n - v.size() <= k;
  41. }
  42.  
  43. main() {
  44.     IO("GIANGSEQ");
  45.     cin >> n >> k;
  46.     for (int i = 1; i <= n; i++) cin >> a[i];
  47.     int l = 0, r = 2e9, mid, res;
  48.     while (l <= r) {
  49.         mid = (l + r) >> 1;
  50.         if (check(mid)) r = --mid;
  51.         else l = ++mid;
  52.     }
  53.     cout << r + 1 << "\n";
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2000000001
https://ideone.com/8yCulu
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!