Submission #1152300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152300		dzuizz	Sjeckanje (COCI21_sjeckanje)	C++20	15 / 110	2096 ms	484 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,q; cin>>n>>q;
	int a[n+1];
	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;
		int dp[n+1];
		dp[0]=0;
		for(int i=1;i<=n;++i){
			dp[i]=dp[i-1];
			int mn=a[i],mx=a[i];
			for(int j=i-1;j>0;--j){
				mn=min(mn,a[j]),mx=max(mx,a[j]);
				dp[i]=max(dp[i],dp[j-1]+(mx-mn));
			}
		}
		cout<<dp[n]<<'\n';
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55