fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(0);cin.tie(0);
  4. #define ll long long
  5. const int maxn = 5e3+5;
  6. int n, K, L;
  7. ll P[maxn];
  8. ll w[maxn];
  9. pair<ll, int> check(ll lambda) {
  10.     vector<pair<ll, int>> dp(n+1,{0,0});
  11.     for(int i = 1; i <= n;i++){
  12.         dp[i] = dp[i-1];
  13.         if(i - L >= 0){
  14.             ll cur = P[i] - P[i-L];
  15.             ll val = dp[i-L].first + cur - lambda;
  16.             int cnt = dp[i-L].second + 1;
  17.             if(val > dp[i].first || (val == dp[i].first && cnt > dp[i].second)){
  18.                 dp[i] = {val, cnt};
  19.             }
  20.         }
  21.     }
  22.     return dp[n];
  23. }
  24. void solve(){
  25.     cin >> n >> K >> L;
  26.     for(int i = 1; i <= n; i++){
  27.         cin >> w[i];
  28.         P[i] = P[i-1] + w[i];
  29.     }
  30.     ll l = -6e12, r = 6e12;
  31.     ll lambda = r;
  32.     while(r - l > 1){
  33.         ll m = l + (r - l) / 2;
  34.         pair<ll, int> it = check(m);
  35.         if(it.second >= K){
  36.             l = m;
  37.             lambda = m;
  38.         } else {
  39.             r = m;
  40.         }
  41.     }
  42.     pair<ll, int> res = check(lambda);
  43.     cout << res.first + lambda*K;
  44. }
  45.  
  46. signed main(){
  47.     fast;
  48.     solve();
  49. }
  50.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rmkEsa
thu hoach alien trick
language:
C++14 (gcc 8.3)
created:
14 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!