oj.uz

답안 #950137

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950137 2024-03-20T05:51:29 Z vjudge1 3단 점프 (JOI19_jumps) C++17
19 / 100
 448 ms 150196 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = (int)5e5+7;
const int M = (int)2e5+7;
const int inf = (int)1e9+7;

int n, q, a[N];
int dp[5003][5003], mx[5003][5003];
int oo[M][20], lo[M];
pair<int, int> pref[N], suf[N];

int get(int l, int r) {
	if(l>r) {
		return -inf;
	}
	int x = lo[r-l+1];
	return max(dp[l][x], dp[r-(1<<x)+1][x]);
}

void solve3() {
	cin >> q >> q >> q;
	for(int i = 2; i < M; ++i) {
		lo[i] = lo[i/2]+1;
	}
	for(int i = 1; i <= n; ++i) {
		oo[i][0] = a[i];
		pref[i] = max(pref[i-1], {a[i], i});
	}
	for(int i = n; i >= 1; --i) {
		suf[i] = max(suf[i+1], {a[i], i});
	}
	for(int i = 2; i < 18; ++i) {
		for(int j = 1; j <= n-(1<<i)+1; ++j) {
			oo[i][j] = max(oo[i][j], oo[i+(1<<(j-1))][j-1]); 
		}
	}
	int ans = 0;
	for(int i = 2; i < n; ++i) {
		int nxt = suf[i+1].second;
		ans = max(ans, a[i]+a[nxt]+get(max(1, i-(nxt-i)), i-1));
		nxt = pref[i-1].second;
		if(i+(i-nxt)<=n) {
			ans = max(ans, a[i]+a[nxt]+get(i+(i-nxt), n));
		}
	}
		
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	} 
	if(n>5000) {
		solve3();
		return 0;
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = i; j <= n; ++j) {
			mx[i][j] = max(mx[i][j-1], a[j]);
		}
	}
	for(int len = 3; len <= n; ++len) {
		for(int i = 1; i <= n-len+1; ++i) {
			int j = i+len-1;
			dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
			int cur = a[i]+a[j];
			int m = (i+j)/2;
			cur += mx[i+1][m];
			dp[i][j] = max(dp[i][j], cur);
		}
	}
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		cout << dp[l][r] << "\n";
	}
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 2 ms 3316 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 2 ms 3316 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 439 ms 149844 KB Output is correct
12 Correct 448 ms 150196 KB Output is correct
13 Correct 422 ms 149828 KB Output is correct
14 Correct 398 ms 149972 KB Output is correct
15 Correct 432 ms 150012 KB Output is correct
16 Correct 408 ms 149644 KB Output is correct
17 Correct 400 ms 149108 KB Output is correct
18 Correct 408 ms 149328 KB Output is correct
19 Correct 434 ms 149928 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 40 ms 47188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 2 ms 3316 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 439 ms 149844 KB Output is correct
12 Correct 448 ms 150196 KB Output is correct
13 Correct 422 ms 149828 KB Output is correct
14 Correct 398 ms 149972 KB Output is correct
15 Correct 432 ms 150012 KB Output is correct
16 Correct 408 ms 149644 KB Output is correct
17 Correct 400 ms 149108 KB Output is correct
18 Correct 408 ms 149328 KB Output is correct
19 Correct 434 ms 149928 KB Output is correct
20 Runtime error 40 ms 47188 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -