Submission #1019403

#TimeUsernameProblemLanguageResultExecution timeMemory
1019403NicolaikrobFeast (NOI19_feast)C++17
100 / 100
198 ms10508 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = 1LL<<50; ll n, k; vector<ll> PS, DP, C; ll sol(ll g) { ll b = PS[n], c = 0; for(int i = 1; i <= n; i++) { if(DP[i-1] >= b-(PS[n]-PS[i])-g) DP[i] = DP[i-1], C[i] = C[i-1]; else DP[i] = b-(PS[n]-PS[i])-g, C[i] = c+1; if(b < DP[i]+PS[n]-PS[i]) b = DP[i]+PS[n]-PS[i], c = C[i]; } return C[n]; } int main() { cin >> n >> k; PS.resize(n+1, 0); DP.resize(n+1, 0); C.resize(n+1, 0); for(int i = 1; i <= n; i++) cin >> PS[i], PS[i] += PS[i-1]; ll l = 0, u = inf; while(l < u) { ll g = (l+u)/2; ll c = sol(g); if(c == k) l = u = g; if(c > k) l = g; if(c < k) u = g; } sol(l); cout << DP[n]+k*l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...