Submission #530592

#	Time	Username	Problem	Language	Result	Execution time	Memory
530592		xuliu	Sjeckanje (COCI21_sjeckanje)	C++17	15 / 110	2074 ms	432 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;

void add(int &a, int b) { a = (a+b)%mod; }
int add(int a, int b, int c) { int res = (((a+b)%mod) + c)%mod; return res; }

ll solve(vector<ll> &a, int n) {
	vector<ll> dp(n, 0);
	for(int i=1; i<n; i++) {
		array<ll, 2> m = {a[i], a[i]};
		dp[i] = dp[i-1];
		for(int j=i-1; j>=0; j--) {
			m[0] = max(m[0], a[j]);
			m[1] = min(m[1], a[j]);
			dp[i] = max(dp[i], (j == 0 ? 0 : dp[j-1]) + (m[0]-m[1]));
		}
	}
	return dp[n-1];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin>>n>>q;
	vector<ll> a(n);
	for(ll &x : a) cin>>x;
	while(q--) {
		int l, r; ll x; cin>>l>>r>>x;
		for(int i=l-1; i<r; i++) a[i] += x;
		cout<<solve(a, n)<<"\n";
	}
}

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