Submission #1152353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152353		thelegendary08	Sjeckanje (COCI21_sjeckanje)	C++17	15 / 110	2096 ms	70980 KiB

Main

#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<long long int>
#define ll long long int
#define mp make_pair
#define pii pair<ll,ll>
#define FOR(i, k, n) for(int i = k; i<n; i++)
using namespace std;
int main(){
	int n; cin>>n; int q; cin>>q;
	vi v(n);
	f0r(i,n)cin>>v[i];
	while(q--){
		int l,r,x;
		cin>>l>>r>>x;
		l--; r--;
		FOR(i, l, r+1)v[i]+=x;
		vector<vi>dp(n, vi(n));
		vi mx(n);
		FOR(i, 1, n){
			ll rmx = -1e18;
			ll rmn = 1e18;
			for(int j = i; j>=0; j--){
				rmx = max(rmx, v[j]);
				rmn = min(rmn, v[j]);
				if(j == 0){
					dp[i][j] = rmx - rmn;
				}
				else{
					dp[i][j] = mx[j-1] + rmx - rmn;
				}
			}
			f0r(j, n){
				mx[i] = max(mx[i], dp[i][j]);
			}
		}
		cout<<mx[n-1]<<'\n';
	}	
}

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