# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
949043 | 2024-03-18T20:49:51 Z | alexdd | Feast (NOI19_feast) | C++17 | 146 ms | 9728 KB |
#include<bits/stdc++.h> using namespace std; #define int long long typedef long double ld; const int INF = 1e9; int n,k; int a[300005]; int dp[300005]; int cnt[300005]; int pref[300005]; ld coef; void solve() { int mxm=0,cate=0; for(int i=1;i<=n;i++) { pref[i] = pref[i-1] + a[i]; dp[i] = dp[i-1]; cnt[i] = cnt[i-1]; int aux = mxm + pref[i] - coef; if(aux>dp[i] || (aux==dp[i] && cate+1>cnt[i])) { dp[i] = aux; cnt[i] = cate+1; } if(dp[i]-pref[i]>mxm || (dp[i]-pref[i]==mxm && cate>cnt[i])) { mxm = dp[i]-pref[i]; cate = cnt[i]; } } } /** dp[i] = max(dp[x] - pref[x]) + pref[i] - coef */ signed main() { cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; int st,dr,ans=0; st=0; dr=n*INF; while(st<=dr) { coef = (st+dr)/2; solve(); if(cnt[n]<=k) { ans=coef; dr=coef-1; } else st=coef+1; } cout<<dp[n] + cnt[n]*coef; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 122 ms | 9584 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 83 ms | 9556 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 146 ms | 9728 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 122 ms | 9584 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |