oj.uz

Submission #950426

# Submission time Handle Problem Language Result Execution time Memory
950426 2024-03-20T09:57:47 Z vjudge1 Triple Jump (JOI19_jumps) C++17
19 / 100
 455 ms 152716 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();
		}
	}
	for(int i = 1; i < n; ++i) {
		int j = r[i]+1;
		if(j <= n) {
			calc(i, j);
		}		
	}
	for(int i = 2; i < n; ++i) {
		int j = l[i]-1;
		if(j >= 1) {
			calc(j, i);
		}
	}
	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 3160 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 1 ms 3160 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 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 3160 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 1 ms 3160 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 455 ms 152640 KB Output is correct
12 Correct 411 ms 152404 KB Output is correct
13 Correct 422 ms 152428 KB Output is correct
14 Correct 443 ms 152716 KB Output is correct
15 Correct 420 ms 152664 KB Output is correct
16 Correct 424 ms 151904 KB Output is correct
17 Correct 442 ms 151892 KB Output is correct
18 Correct 427 ms 151940 KB Output is correct
19 Correct 443 ms 152356 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8796 KB Output is correct
2 Correct 18 ms 8792 KB Output is correct
3 Correct 18 ms 9816 KB Output is correct
4 Correct 19 ms 8796 KB Output is correct
5 Correct 20 ms 8796 KB Output is correct
6 Correct 18 ms 8904 KB Output is correct
7 Incorrect 19 ms 8540 KB Output isn't correct
8 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 3160 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 1 ms 3160 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Correct 455 ms 152640 KB Output is correct
12 Correct 411 ms 152404 KB Output is correct
13 Correct 422 ms 152428 KB Output is correct
14 Correct 443 ms 152716 KB Output is correct
15 Correct 420 ms 152664 KB Output is correct
16 Correct 424 ms 151904 KB Output is correct
17 Correct 442 ms 151892 KB Output is correct
18 Correct 427 ms 151940 KB Output is correct
19 Correct 443 ms 152356 KB Output is correct
20 Correct 20 ms 8796 KB Output is correct
21 Correct 18 ms 8792 KB Output is correct
22 Correct 18 ms 9816 KB Output is correct
23 Correct 19 ms 8796 KB Output is correct
24 Correct 20 ms 8796 KB Output is correct
25 Correct 18 ms 8904 KB Output is correct
26 Incorrect 19 ms 8540 KB Output isn't correct
27 Halted 0 ms 0 KB -