Submission #468536

#	Time	Username	Problem	Language	Result	Execution time	Memory
468536		mosiashvililuka	Sjeckanje (COCI21_sjeckanje)	C++14	15 / 110	2080 ms	460 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],pas,dp[200009];
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	for(i=1; i<=a; i++){
		cin>>f[i];
	}
	for(t=1; t<=tes; t++){
		cin>>c>>d>>e;
		for(i=c; i<=d; i++) f[i]+=e;
		pas=0;
		/*for(i=2; i<=a; i++){
			pas+=abs(f[i]-f[i-1]);
			if((i!=a&&f[i]>=f[i-1]&&f[i]>=f[i+1])||(i!=a&&f[i]<=f[i-1]&&f[i]<=f[i+1])){
				pas-=min(abs(f[i]-f[i-1]),abs(f[i]-f[i+1]));
			}
		}
		cout<<pas<<"\n";*/
		for(i=1; i<=a; i++){
			zx=f[i];xc=f[i];dp[i]=0;
			for(j=i; j>=1; j--){
				zx=min(zx,f[j]);xc=max(xc,f[j]);
				dp[i]=max(dp[i],dp[j-1]+xc-zx);
			}
		}
		cout<<dp[a]<<"\n";
	}
	return 0;
}

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