oj.uz

Submission #950150

# Submission time Handle Problem Language Result Execution time Memory
950150 2024-03-20T05:55:40 Z vjudge1 Triple Jump (JOI19_jumps) C++17
19 / 100
 400 ms 150004 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(oo[l][x], oo[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[j][i] = max(oo[j][i-1], oo[j+(1<<(i-1))][i-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 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 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 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 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 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 382 ms 149872 KB Output is correct
12 Correct 384 ms 149740 KB Output is correct
13 Correct 397 ms 149764 KB Output is correct
14 Correct 384 ms 149820 KB Output is correct
15 Correct 394 ms 150004 KB Output is correct
16 Correct 390 ms 149140 KB Output is correct
17 Correct 398 ms 149196 KB Output is correct
18 Correct 400 ms 149372 KB Output is correct
19 Correct 381 ms 149924 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 23388 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 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 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 382 ms 149872 KB Output is correct
12 Correct 384 ms 149740 KB Output is correct
13 Correct 397 ms 149764 KB Output is correct
14 Correct 384 ms 149820 KB Output is correct
15 Correct 394 ms 150004 KB Output is correct
16 Correct 390 ms 149140 KB Output is correct
17 Correct 398 ms 149196 KB Output is correct
18 Correct 400 ms 149372 KB Output is correct
19 Correct 381 ms 149924 KB Output is correct
20 Incorrect 32 ms 23388 KB Output isn't correct
21 Halted 0 ms 0 KB -