oj.uz

Submission #950137

# Submission time Handle Problem Language Result Execution time Memory
950137 2024-03-20T05:51:29 Z vjudge1 Triple Jump (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -