Submission #1142673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142673		sayan	Sjeckanje (COCI21_sjeckanje)	C++20	55 / 110	2095 ms	22544 KiB

Main

#include <bits/stdc++.h>
#define Sayan ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define sz() size()
#define F first
#define S second
#define pb push_back
#define yes cout << "YES\n"
#define no cout << "NO\n"
using namespace std ;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const ll N = 2e5+5;
const ll inf = 1e18;
const int mod = 1e9+7; // 998244353;
//////////////////////////////////////////////////////
ll TEST=0;
ll a[N] , dp[N];
//////////////////////////////////////////////////////
struct delai{
	// ll l,r;
};

//////////////////////////////////////////////////////
void solve(){
	ll n,q;
	cin>>n>>q;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
	}

	while(q--){
		ll l,r,x;
		cin>>l>>r>>x;
		for(ll i=l;i<=r;i++){
			a[i]+=x;
		}
		multiset<ll>st,st2;
		for(ll i=1;i<=n;i++){
			if(i>=2){
				ll to=*st.rbegin();
				ll to2=*st2.rbegin();
				dp[i]=max({dp[i-1],to+a[i],to2-a[i]});	
			}
			st.insert(dp[i-1]-a[i]);
			st2.insert(dp[i-1]+a[i]);
		}
		cout<<dp[n]<<'\n';
	}
}
signed main () {
	Sayan;
	ll t=1;
	if(TEST){
		cin>>t;	
	}
	while(t--)solve();
}

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