Submission #1188078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188078		qrn	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	8 ms	320 KiB

Main

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt int

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e9;
const intt mxN = 5e5 + 5;
const intt L = 21;

void solve() {
	intt N, Q;
	cin >> N >> Q;
	vector<intt> A(N);
	for(auto &a : A) cin >> a;
	while(Q--){ 
		intt l, r, val;
		cin >> l >> r >> val;
		--l; --r;
		for(intt i = l; i <= r; i++) {
			A[i] += val;
		}
		vector<intt> dp(N, 0ll);
		dp[0] = 0;
		// for(intt i = 0; i < N; i++) {
		// 	cout << A[i] << " ";
		// }
		// cout << endl;
		for(intt i = 1; i < N; i++) {
			intt maks = A[i], mini = A[i];
			for(intt j = i - 1; j >= 0; j--) {
				maks = max(maks, A[j]);
				mini = min(mini, A[j]);
				if(j - 1 >= 0)
				dp[i] = max(dp[i], dp[j-1] + abs(maks - mini));
				else 
				dp[i] = max(dp[i], abs(maks - mini));
				// if(i == 3 && j == 2) {
				// 	cout << maks << " " << mini << " ALKSNFKL" << endl;
				// }
			}
		}
		cout << dp[N-1] << endl;
	}
}

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1;
	// cin >> tst;
	while(tst--) {
		solve();
	}
}

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