oj.uz

Submission #160267

# Submission time Handle Problem Language Result Execution time Memory
160267 2019-10-26T16:09:00 Z iefnah06 Triple Jump (JOI19_jumps) C++11
19 / 100
 428 ms 77304 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5010;
int N;
int A[MAXN];

int best[MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int l = 0; l < N; l++) {
		int maxval = 0;
		for (int r = l+2; r <= N; r++) {
			if ((r-l) % 2 == 1) {
				maxval = max(maxval, A[l + (r-l-1) / 2]);
			}
			best[l][r] = A[l] + A[r-1] + maxval;
		}
	}
	for (int l = N-1; l >= 0; l--) {
		for (int r = l+2; r <= N; r++) {
			if (r+1 <= N) {
				best[l][r+1] = max(best[l][r+1], best[l][r]);
			}
			if (l-1 >= 0) {
				best[l-1][r] = max(best[l-1][r], best[l][r]);
			}
		}
	}

	int Q; cin >> Q;
	while (Q--) {
		int l, r; cin >> l >> r; l--;
		cout << best[l][r] << '\n';
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 339 ms 77180 KB Output is correct
12 Correct 344 ms 77048 KB Output is correct
13 Correct 343 ms 77224 KB Output is correct
14 Correct 348 ms 77176 KB Output is correct
15 Correct 337 ms 77304 KB Output is correct
16 Correct 428 ms 76508 KB Output is correct
17 Correct 367 ms 76388 KB Output is correct
18 Correct 331 ms 76536 KB Output is correct
19 Correct 333 ms 77048 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 352 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 339 ms 77180 KB Output is correct
12 Correct 344 ms 77048 KB Output is correct
13 Correct 343 ms 77224 KB Output is correct
14 Correct 348 ms 77176 KB Output is correct
15 Correct 337 ms 77304 KB Output is correct
16 Correct 428 ms 76508 KB Output is correct
17 Correct 367 ms 76388 KB Output is correct
18 Correct 331 ms 76536 KB Output is correct
19 Correct 333 ms 77048 KB Output is correct
20 Runtime error 52 ms 688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -