Submission #522835

#TimeUsernameProblemLanguageResultExecution timeMemory
522835julian33Sjeckanje (COCI21_sjeckanje)C++14
15 / 110
2070 ms448 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mxN=2e5+5; ll a[mxN],dp[mxN]; int main(){ cin.sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,q; cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; while(q--){ int l,r,x; cin>>l>>r>>x; for(int i=l;i<=r;i++) a[i]+=x; // for(int i=1;i<=n;i++){ // dp[i]=dp[i-1]; // if(i>1) dp[i]=max(dp[i],dp[i-2]+abs(a[i]-a[i-1])); // if(i>2) dp[i]=max(dp[i],dp[i-3]+max(abs(a[i]-a[i-1]),max(abs(a[i]-a[i-2]),abs(a[i-1]-a[i-2])))); // } for(int i=1;i<=n;i++){ ll lo=1e18; ll hi=-1e18; dp[i]=0; for(int j=i-1;j>=0;j--){ lo=min(lo,a[j+1]); hi=max(hi,a[j+1]); dp[i]=max(dp[i],hi-lo+dp[j]); } } cout<<dp[n]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...