Submission #1283660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283660		hccoder	Sjeckanje (COCI21_sjeckanje)	C++20	55 / 110	2095 ms	19780 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, q; cin>>n>>q;
	vector<long long> a(n+1);
	for (int i = 1; i<=n; i++) cin>>a[i];
	while(q--){
	    int l, r, x; cin>>l>>r>>x;
	    for (int i = l; i<=r; i++) a[i]+=x;
	    set<long long> st1{a[1]}, st2{-a[1]};
	    vector<long long> dp(n+1);
	    for (int i = 1; i<=n; i++){
	        dp[i] = max(dp[i], dp[i-1]);
	        dp[i] = max(dp[i], *prev(st1.end())-a[i]);
	        dp[i] = max(dp[i], *prev(st2.end())+a[i]);
	        if (i!=n){
	            st1.insert(dp[i] + a[i+1]);
    	        st2.insert(dp[i] - a[i+1]);   
	        }
	    }
	    cout<<dp[n]<<"\n";
	}
}

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