fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
  4. #define fi first
  5. #define se second
  6. #define el "\n"
  7. #define pb push_back
  8. #define sz(a) (int)a.size()
  9. #define FILL(a, x) memset(a, x, sizeof(a))
  10.  
  11. using namespace std;
  12. typedef long long ll;
  13. typedef pair<int, int> ii;
  14. const int N = (int)1e6+3;
  15.  
  16. struct P2{ ll val; int cnt; };
  17.  
  18. int n, K;
  19. ll Pneed;
  20. vector<ll> x, w, pref, seg;
  21. vector<int> rgt, nxti;
  22. vector<P2> dp;
  23.  
  24. inline P2 best(P2 a, P2 b){
  25.     if(a.val != b.val) return (a.val > b.val) ? a : b;
  26.     return (a.cnt < b.cnt) ? a : b;
  27. }
  28.  
  29. P2 run_dp(ll lam){
  30.     int m = n;
  31.     dp[m+1].val = 0; dp[m+1].cnt = 0;
  32.     for(int i = m; i >= 1; --i){
  33.         P2 skip = dp[i+1];
  34.         P2 take;
  35.         take.val = seg[i] - lam + dp[nxti[i]].val;
  36.         take.cnt = 1 + dp[nxti[i]].cnt;
  37.         dp[i] = best(skip, take);
  38.     }
  39.     return dp[1];
  40. }
  41.  
  42. bool ok(ll L){
  43.     int j = 1;
  44.     for(int i = 1; i <= n; ++i){
  45.         while(j <= n && x[j] - x[i] <= L) ++j;
  46.         rgt[i] = j - 1;
  47.     }
  48.     for(int i = 1; i <= n; ++i){
  49.         nxti[i] = rgt[i] + 1;
  50.         seg[i] = pref[rgt[i]] - pref[i-1];
  51.     }
  52.  
  53.     ll sumAll = pref[n];
  54.     if(sumAll < Pneed) return false;
  55.  
  56.     ll lo = 0, hi = sumAll, mid;
  57.     while(lo < hi){
  58.         mid = (lo + hi) >> 1;
  59.         P2 res = run_dp(mid);
  60.         if(res.cnt <= K) hi = mid; else lo = mid + 1;
  61.     }
  62.     P2 finalRes = run_dp(lo);
  63.     ll bestWithAtMostK = finalRes.val + lo * (ll)K;
  64.     return bestWithAtMostK >= Pneed;
  65. }
  66.  
  67. int main(){
  68.     ios_base::sync_with_stdio(false);
  69.     cin.tie(NULL); cout.tie(NULL);
  70.  
  71.  
  72.     cin >> n >> K >> Pneed;
  73.     x.assign(n+1,0); w.assign(n+1,0);
  74.     for(int i=1;i<=n;++i){ cin >> x[i] >> w[i]; }
  75.  
  76.     pref.assign(n+1,0);
  77.     for(int i=1;i<=n;++i) pref[i] = pref[i-1] + w[i];
  78.  
  79.     rgt.assign(n+2,0);
  80.     nxti.assign(n+2,0);
  81.     seg.assign(n+2,0);
  82.     dp.assign(n+2, {0,0});
  83.  
  84.     ll Llo = 0;
  85.     ll Lhi = x[n] - x[1];
  86.     ll ans = -1;
  87.  
  88.     while(Llo <= Lhi){
  89.         ll Lmid = (Llo + Lhi) >> 1;
  90.         if(ok(Lmid)){
  91.             ans = Lmid;
  92.             Lhi = Lmid - 1;
  93.         }else{
  94.             Llo = Lmid + 1;
  95.         }
  96.     }
  97.  
  98.     cout << ans << el;
  99.     return 0;
  100. }
  101.  
  102.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/nuZUgY
language:
C++14 (clang 8.0)
created:
6 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!