Submission #1167623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167623		WH8	Sjeckanje (COCI21_sjeckanje)	C++20	55 / 110	15 ms	584 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)

#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
int mem[5005], a[5005], d[5005];
bool samesign(int a, int b){
	if((a<=0 and b<=0) or (a>0 and b>0))return true;
	return false;
}
signed main(){
	int n,q;cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(i>=1)d[i]=a[i]-a[i-1];
	}
	
	for(int i=0;i<q;i++){
		int l,r,c;cin>>l>>r>>c;
		l--,r--;
		d[l]+=c;
		d[r+1]-=c;
		//~ cout<<endl;
		//~ for(int j=0; j<n;j++)cout<<d[j]<<" ";
		//~ cout<<endl;
		fill(mem,mem+n+1,0);
		mem[1]=abs(d[1]);
		for(int j=2;j<n;j++){
			if(samesign(d[j-1], d[j])){
				mem[j]=mem[j-1]+abs(d[j]);
			}
			else{
				mem[j]=max(mem[j-2]+abs(d[j]),mem[j-1]);
			}
		}
		cout<<mem[n-1]<<endl;
	}
	
}

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