Submission #1025666

#TimeUsernameProblemLanguageResultExecution timeMemory
1025666ach00Feast (NOI19_feast)C++14
0 / 100
1038 ms40288 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,k; vector<ll> W; vector<vector<ll>> dp(2, vector<ll>(300005, -1)); vector<vector<ll>> dpcnt(2, vector<ll>(300005, -1)); ll pen; ll solve(bool w, int i) { if(dp[w][i] != -1) return dp[w][i]; if(i >= n) return 0; ll ans = numeric_limits<int>::min(); if(w == false) { if(solve(false, i+1) > ans) { dpcnt[w][i] = dpcnt[w][i+1]; ans = solve(false, i+1); } if(-pen + solve(true, i+1) > ans) { dpcnt[w][i] = 1 + dpcnt[w][i+1]; ans = -pen + solve(true, i+1); } } else { if(W[i] + solve(false, i+1) > ans) { dpcnt[w][i] = dpcnt[w][i+1]; ans = W[i] + solve(false, i+1); } if(W[i] + solve(true, i+1) > ans) { dpcnt[w][i] = dpcnt[w][i+1]; ans = W[i] + solve(true, i+1); } } dp[w][i] = ans; return ans; } int main() { cin >> n >> k; W.resize(n); for(int i = 0; i < n; i++) { cin >> W[i]; } pen = 0; ll lower = 0; ll upper = numeric_limits<ll>::max(); while(lower < upper) { ll mid = (lower + upper)/2; pen = mid; dp = vector<vector<ll>>(2, vector<ll>(300005, -1)); dpcnt = vector<vector<ll>>(2, vector<ll>(300005, -1)); ll start = solve(true, 0); ll dstart = solve(false, 0); if(start >= dstart) { int cnt = dpcnt[true][0]; if(cnt > k) { lower = mid; } else { upper = mid; } } else { int cnt = dpcnt[true][0]; if(cnt > k) { lower = mid; } else { upper = mid; } } } pen = lower; ll start = solve(true, 0); ll dstart = solve(false, 0); ll cnt; if(start >= dstart) cnt = dpcnt[true][0]; else cnt = dpcnt[false][0]; cout << max(start, dstart) + cnt*pen; }
#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...