oj.uz

Submission #950402

# Submission time Handle Problem Language Result Execution time Memory
950402 2024-03-20T09:25:49 Z vjudge1 Triple Jump (JOI19_jumps) C++17
19 / 100
 398 ms 150132 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];
pair<int, int> suf[N];
int l[N], r[N];

void solve3() {
	cin >> q >> q >> q;
	for(int i = n; i >= 1; --i) {
		suf[i] = max(suf[i+1], {a[i], i});
	}                                  	
	stack<int> st;
	for(int i = 1; i <= n; ++i) {
		l[i] = i;
		while(!st.empty() && a[st.top()]<=a[i]) {
		    l[i]=l[st.top()];
			st.pop();
		}
		st.push(i);
	}
	while(!st.empty()) {
		continue;
	}
	for(int i = n; i >= 1; --i) {
		r[i] = i;
		while(!st.empty() && a[st.top()]<=a[i]) {
			r[i] = r[st.top()];
			st.pop();
		}
	}
	int ans = 0;
	for(int j = 2; j < n; ++j) {
		for(int i = l[j]-1; i >= l[j]-1; --i) {
			int o = (j-i);
			if(i>0 && r[i]<j && j+o <= n) {
				ans = max(ans, a[i]+a[j]+suf[j+o].first);
			}
		}
	}		
	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 2392 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 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3416 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 2392 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 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3416 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 379 ms 150024 KB Output is correct
12 Correct 392 ms 150096 KB Output is correct
13 Correct 371 ms 150096 KB Output is correct
14 Correct 398 ms 150080 KB Output is correct
15 Correct 398 ms 150132 KB Output is correct
16 Correct 375 ms 149328 KB Output is correct
17 Correct 388 ms 149248 KB Output is correct
18 Correct 398 ms 149344 KB Output is correct
19 Correct 373 ms 149844 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 7772 KB Output is correct
2 Incorrect 17 ms 9556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 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 3164 KB Output is correct
6 Correct 1 ms 3164 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3416 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 379 ms 150024 KB Output is correct
12 Correct 392 ms 150096 KB Output is correct
13 Correct 371 ms 150096 KB Output is correct
14 Correct 398 ms 150080 KB Output is correct
15 Correct 398 ms 150132 KB Output is correct
16 Correct 375 ms 149328 KB Output is correct
17 Correct 388 ms 149248 KB Output is correct
18 Correct 398 ms 149344 KB Output is correct
19 Correct 373 ms 149844 KB Output is correct
20 Correct 18 ms 7772 KB Output is correct
21 Incorrect 17 ms 9556 KB Output isn't correct
22 Halted 0 ms 0 KB -