oj.uz

Submission #940588

# Submission time Handle Problem Language Result Execution time Memory
940588 2024-03-07T11:08:34 Z SamNguyen Sjeckanje (COCI21_sjeckanje) C++14
15 / 110
 2000 ms 2616 KB 
#include <bits/stdc++.h>
using namespace std;

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
	if (x > y) { x = y; return true; }
	return false;
}

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
	if (x < y) { x = y; return true; }
	return false;
}

const int MAX = 2e5 + 7;
int N, Q;
long long arr[MAX];

void input() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
}

void init() {
}

void update(int l, int r, long long x) {
	for (int i = l; i <= r; i++)
		arr[i] += x;
}

long long dp[MAX];

long long get() {
	dp[0] = 0;
	for (int i = 1; i <= N; i++) {
		long long min_v = arr[i], max_v = arr[i];;
		dp[i] = dp[i - 1];
		for (int j = i; j > 0; j--) {
			minimise(min_v, arr[j]);
			maximise(max_v, arr[j]);
			maximise(dp[i], dp[j - 1] + max_v - min_v);
		}
	}
	return dp[N];
}
	
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	init();

	while (Q--) {
		int l, r; cin >> l >> r;
		long long x; cin >> x;
		update(l, r, x);
		cout << get() << '\n';
	}

	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 7 ms 2396 KB Output is correct
3 Correct 7 ms 2396 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 6 ms 2516 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 7 ms 2396 KB Output is correct
3 Correct 7 ms 2396 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 6 ms 2516 KB Output is correct
7 Execution timed out 2049 ms 2616 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 7 ms 2396 KB Output is correct
3 Correct 7 ms 2396 KB Output is correct
4 Correct 6 ms 2392 KB Output is correct
5 Correct 6 ms 2396 KB Output is correct
6 Correct 6 ms 2516 KB Output is correct
7 Execution timed out 2049 ms 2616 KB Time limit exceeded
8 Halted 0 ms 0 KB -