Submission #727196

#TimeUsernameProblemLanguageResultExecution timeMemory
727196PenguinsAreCuteFeast (NOI19_feast)C++17
100 / 100
229 ms10444 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define mp make_pair #define pb push_back #define LL_MAX LONG_LONG_MAX #define LL_MIN LONG_LONG_MIN #define speed ios_base::sync_with_stdio(false); cin.tie(0) #define stMx(a,b) a = max(a,b) #define stMn(a,b) a = min(a,b) typedef pair<int,int> ii; typedef vector<int> vi; typedef set<int> si; typedef vector<ii> vii; typedef set<ii> sii; #define REP(i, a, b) for(int i = a; i < b; i++) int32_t main() { int N, K; cin >> N >> K; int A[N+1]; A[0]=0; REP(i,1,N+1) { cin>>A[i]; A[i]+=A[i-1]; //cerr<<i<<" "<<A[i]<<"\n"; } ii dp[N+1]; int l = -1, h = 300000000000005; while(h-l>1){ dp[0]=mp(0,0); int lambda = (l+h)/2; //printf("Attempting lambda=%lld\n",lambda); ii best = mp(0,0); // value, -1 * subarrs REP(i,1,N+1) { //printf("%lld %lld %lld\n",A[i],best.fi,lambda); dp[i]=max(dp[i-1],mp(A[i]+best.fi-lambda,best.se-1)); //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se); //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se); stMx(best,mp(dp[i].fi-A[i],dp[i].se)); //printf("best is now %lld %lld\n",best.fi,best.se); } if(dp[N].se>=-1*K) h=lambda; else l=lambda; //REP(i,1,N+1){ // cerr<<i<<" "<<A[i]<<"\n"; //} } ii best = mp(0,0); // value, -1 * subarrs REP(i,1,N+1) { //printf("%lld %lld %lld\n",A[i],best.fi,lambda); dp[i]=max(dp[i-1],mp(A[i]+best.fi-h,best.se-1)); //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se); //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se); stMx(best,mp(dp[i].fi-A[i],dp[i].se)); //printf("best is now %lld %lld\n",best.fi,best.se); } cout << dp[N].fi+h*K; }
#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...