oj.uz

Submission #679745

# Submission time Handle Problem Language Result Execution time Memory
679745 2023-01-09T06:20:08 Z parsadox2 Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 105 ms 596 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 94 ms 464 KB Output is correct
8 Correct 103 ms 460 KB Output is correct
9 Correct 105 ms 480 KB Output is correct
10 Correct 101 ms 472 KB Output is correct
11 Correct 98 ms 468 KB Output is correct
12 Correct 70 ms 480 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 94 ms 464 KB Output is correct
8 Correct 103 ms 460 KB Output is correct
9 Correct 105 ms 480 KB Output is correct
10 Correct 101 ms 472 KB Output is correct
11 Correct 98 ms 468 KB Output is correct
12 Correct 70 ms 480 KB Output is correct
13 Runtime error 2 ms 596 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -