Submission #679745

#	Time	Username	Problem	Language	Result	Execution time	Memory
679745		parsadox2	Sjeckanje (COCI21_sjeckanje)	C++14	55 / 110	105 ms	596 KiB

Main

#include <bits/stdc++.h>
#define pb 		push_back
#define F		first
#define S 		second
#define debug(x)    cout << #x << "= " << x << ", "
#define ll 		long long
#define fast 		ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0)
#define SZ(x)         (int) x.size()
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e3 + 10 , mod = 1e9 + 7;

int n , q , ar[maxn] , dp[maxn] , sum;
bool marked[maxn];

void update(int x)
{
	if(x <= 0 || x + 1 >= n)
		return;
	if(ar[x] >= ar[x - 1] && ar[x] >= ar[x + 1])
		marked[x] = true;
	else if(ar[x] <= ar[x - 1] && ar[x] <= ar[x + 1])
		marked[x] = true;
	else
		marked[x] = false;
}

void update_dp()
{
	sum = 0;
	for(int i = 1 ; i < n ; i++)
		sum += abs(ar[i] - ar[i - 1]);
	for(int i = 1 ; i < n - 1 ; i++)
		update(i);
	for(int i = 1 ; i < n ; i++)
	{
		if(!marked[i])
		{
			dp[i] = dp[i - 1];
			continue;
		}
		if(!marked[i - 1])
		{
			dp[i] = dp[i - 1] + min(abs(ar[i] - ar[i - 1]) , abs(ar[i] - ar[i + 1]));
			continue;
		}
		dp[i] = dp[i - 1] + abs(ar[i] - ar[i + 1]);
		dp[i] = min(dp[i] , dp[i - 2] + abs(ar[i] - ar[i - 1]));
	}
}

int32_t main()
{
	fast;
	
	cin >> n >> q;
	for(int i = 0 ; i < n ; i++)
		cin >> ar[i];
	while(q--)
	{
		int l , r , x;
		cin >> l >> r >> x;
		l--;  r--;
		for(int i = l ; i <= r ; i++)
			ar[i] += x;
		update_dp();
		cout << sum - dp[n - 1] << '\n';
	}
	return 0;
}

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