답안 #160267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160267	2019-10-26T16:09:00 Z	iefnah06	3단 점프 (JOI19_jumps)	C++11	19 / 100	428 ms	77304 KB

jumps

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-