Submission #1152462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152462		dzuizz	Sjeckanje (COCI21_sjeckanje)	C++20	55 / 110	2093 ms	3644 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define DEBUG
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,q; cin>>n>>q;
	
	int a[n]; for(auto&x:a) cin>>x;
	int d[n]; for(int i=1;i<n;++i) d[i]=a[i]-a[i-1];
	
	while(q--){
		if(n==1){ cout<<"0\n"; continue; }
		
		int l,r,x; cin>>l>>r>>x;
		d[--l]+=x,d[r]-=x;
#ifdef DEBUG
		for(auto&x:d) cout<<x<<" ";
		cout<<'\n';
#endif
		int pp=0, p=abs(d[1]);
		for(int i=2;i<n;++i){
			int take=max(pp,(d[i-1]>0)==(d[i]>0)?p:0)+abs(d[i]);
			int notake=max(pp,p);
			pp=notake,p=take;
		}
		cout<<max(pp,p)<<'\n';
	}
	return 0;
}

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