Submission #1203431

#TimeUsernameProblemLanguageResultExecution timeMemory
1203431tritranminh2808Art Exhibition (JOI18_art)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int pp=5e5+5; int a[pp],b[pp],n; struct pl{ int val,s,maxx,minn; }; pl dp[2][pp]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=1;i<=n;i++) cin >> a[i] >> b[i]; dp[1][1].val=b[1]; dp[1][1].minn=a[1]; dp[1][1].maxx=a[1]; dp[1][1].s=b[1]; dp[0][1].val=-1e18; dp[0][1].minn=1e18; dp[0][1].maxx=-1e18; dp[0][1].s=-1e18; for(int i=2;i<=n;i++){ int prmax=0,prmin=0,prs=0,prval=0; if(dp[0][i-1].val<dp[1][i-1].val){ prval=dp[1][i-1].val; prmin=dp[1][i-1].minn; prmax=dp[1][i-1].maxx; prs=dp[1][i-1].s; } else{ prval=dp[0][i-1].val; prmin=dp[0][i-1].minn; prmax=dp[0][i-1].maxx; prs=dp[0][i-1].s; } dp[0][i].val=prval; dp[0][i].maxx=prmax; dp[0][i].minn=prmin; dp[0][i].s=prs; int cmax=0,cmin=0; if(a[i]>prmax) cmax=a[i]; else cmax=prmax; if(a[i]<prmin) cmin=a[i]; else cmin=prmin; dp[1][i].val=prs+b[i]-cmax+cmin; dp[1][i].minn=cmin; dp[1][i].maxx=cmax; dp[1][i].s=prs+b[i]; } cout << max(dp[0][n].val,dp[1][n].val); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...