Submission #1255112

#TimeUsernameProblemLanguageResultExecution timeMemory
1255112DanielPr8Feast (NOI19_feast)C++20
4 / 100
29 ms9796 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector<ll>; using vvl = vector<vll>; using vb = vector<bool>; using pll = pair<ll,ll>; using vpl = vector<pll>; using vvp = vector<vpl>; #define f first #define s second #define pb push_back #define all(v) v.begin(),v.end() vll a, rs; ll n; pll calc(ll lam){ vpl dp(n+1); pll mx={0,0}; for(ll i = 1; i<=n; ++i){ dp[i] = max<pll>(dp[i-1], {mx.f+rs[i]-lam, mx.s-1}); mx = max<pll>(mx, {dp[i].f-rs[i], dp[i].s}); } return dp[n]; } int main(){ ios_base::sync_with_stdio(0);cin.tie(NULL); ll k; cin >> n >> k; a = vll(n); rs = vll(n+1); for(ll i = 0; i < n; ++i){ cin >> a[i]; rs[i+1]=rs[i]+a[i]; } ll ans; ll s=0, e=1e1; while(s<e){ pll ret = calc((s+e)/2); if(-ret.s>k)s=(s+e)/2+1; else{ans=ret.f+k*((s+e)/2);e=(s+e)/2;} } cout << ans; }
#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...