제출 #160267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160267		iefnah06	3단 점프 (JOI19_jumps)	C++11	19 / 100	428 ms	77304 KiB

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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54