fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pii pair<int,int>
  5. const int N=2e5+5;
  6. pii dp[N];
  7. int n,k,s;
  8. int a[N],pre[N];
  9. int check(int pen){
  10.     int l=0;
  11.     for(int i=1; i<=n; i++){
  12.         dp[i]=make_pair(dp[i-1].first+pen,dp[i-1].second+1);
  13.         if(i>1) dp[i]=max(dp[i],dp[i-1]);
  14.         while(l<i && pre[i]-pre[l+1]>=s) l++;
  15.         if(pre[i]-pre[l]>=s){
  16.             dp[i]=max(dp[i],make_pair(dp[l].first+1+pen,dp[l].second+1));
  17.         }
  18.     }
  19. //    cerr<<pen<<' '<<dp[n].sl<<'\n';
  20.     return dp[n].second;
  21. }
  22. void Solve(){
  23.     cin>>n>>k>>s;
  24.     for(int i=1; i<=n; i++){
  25.         cin>>a[i];
  26.         pre[i]=pre[i-1]+a[i];
  27.     }
  28.     int l=-n,r=n,m,kq=-1e9;
  29.     dp[0]={0,0};
  30.     int sl=0;
  31.     while(l<=r){
  32.         m=(l+r)/2;
  33.         if(check(m)>=k){
  34.             r=m-1;
  35.             kq=m;
  36.         }
  37.         else{
  38.             l=m+1;
  39.         }
  40.     }
  41.     check(kq);
  42.     cout<<dp[n].first-k*kq<<'\n';
  43. }
  44. signed main(){
  45.      freopen("SKS.inp","r",stdin);
  46.      freopen("SKS.out","w",stdout);
  47.     ios_base::sync_with_stdio(0);
  48.     cin.tie(0); cout.tie(0);
  49.     int Cases=1;
  50.      cin>>Cases;
  51.     while(Cases--){
  52.         Solve();
  53.     }
  54. }
  55.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/L01LiS
language:
C++ (gcc 8.3)
created:
15 hours 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!