Submission #1152605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152605		gelastropod	Sjeckanje (COCI21_sjeckanje)	C++20	15 / 110	2094 ms	524 KiB

Main

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

signed main() {
	int n, q, x, l, r;
	cin >> n >> q;
	vector<int> A;
	for (int i = 0; i < n; i++) {
		cin >> x;
		A.push_back(x);
	}
	for (int i = 0; i < q; i++) {
		cin >> l >> r >> x;
		l--, r--;
		for (int j = l; j <= r; j++)
			A[j] += x;
		vector<int> dp;
		dp.push_back(0);
		for (int j = 0; j < n; j++) {
			int crntmax = -1;
			int cmin = A[j], cmax = A[j];
			for (int k = j; k >= 0; k--) {
				cmax = max(cmax, A[k]);
				cmin = min(cmin, A[k]);
				crntmax = max(crntmax, dp[k] + cmax - cmin);
			}
			dp.push_back(crntmax);
		}
		cout << dp.back() << '\n';
	}
}

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