oj.uz

Submission #950596

# Submission time Handle Problem Language Result Execution time Memory
950596 2024-03-20T13:22:06 Z vjudge1 Triple Jump (JOI19_jumps) C++17
19 / 100
 437 ms 154452 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];
int ans;

void calc(int i, int j) {
	if(j+(j-i)<=n) {
		ans = max(ans, a[i]+a[j]+suf[j+(j-i)].first);
	}
}

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();
		}
st.push(i);
	}
	for(int i = 1; i < n; ++i) {
		int j = r[i]+1;
		if(j <= n) {
			calc(i, j);
		}		
	}
	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 3416 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3284 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3284 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 3416 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3284 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3284 KB Output is correct
11 Correct 437 ms 154452 KB Output is correct
12 Correct 399 ms 154196 KB Output is correct
13 Correct 398 ms 154452 KB Output is correct
14 Correct 406 ms 154420 KB Output is correct
15 Correct 398 ms 154340 KB Output is correct
16 Correct 405 ms 153680 KB Output is correct
17 Correct 395 ms 153600 KB Output is correct
18 Correct 436 ms 153616 KB Output is correct
19 Correct 395 ms 154264 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 9708 KB Output isn't correct
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 3416 KB Output is correct
5 Correct 1 ms 3164 KB Output is correct
6 Correct 1 ms 3284 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3284 KB Output is correct
11 Correct 437 ms 154452 KB Output is correct
12 Correct 399 ms 154196 KB Output is correct
13 Correct 398 ms 154452 KB Output is correct
14 Correct 406 ms 154420 KB Output is correct
15 Correct 398 ms 154340 KB Output is correct
16 Correct 405 ms 153680 KB Output is correct
17 Correct 395 ms 153600 KB Output is correct
18 Correct 436 ms 153616 KB Output is correct
19 Correct 395 ms 154264 KB Output is correct
20 Incorrect 23 ms 9708 KB Output isn't correct
21 Halted 0 ms 0 KB -