oj.uz

Submission #489489

# Submission time Handle Problem Language Result Execution time Memory
489489 2021-11-23T03:48:08 Z 8e7 Triple Jump (JOI19_jumps) C++17
19 / 100
 406 ms 72724 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 5005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], pref[maxn], suf[maxn], sp[19][maxn];
int ans[maxn][maxn];
pii ma[maxn];
int getma(int l, int r) {
	if (r < l) return 0;
	int len = __lg(r - l + 1);
	return max(sp[len][l], sp[len][r - (1<<len)+1]); 
}
int main() {
	io
	int n, q;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i], ma[i] = {a[i], i}, sp[0][i] = a[i];
	for (int i = 1;i <= n;i++) pref[i] = max(a[i], pref[i-1]);
	for (int i = n;i >= 1;i--) suf[i] = max(a[i], suf[i+1]);
	//sort(ma + 1, ma + n + 1, [&](pii x, pii y){return x.ff > y.ff;});
	for (int i = 1;i < 19;i++) {
		for (int j = 1;j <= n - (1<<i)+1;j++) {
			sp[i][j] = max(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = i + 2;j <= n;j++) {
			ans[i][j] = a[i] + a[j] + getma(i+1, (i+j)/2);
		}
	}
	for (int i = 2;i <= n;i++) {
		for (int j = 1;i + j <= n;j++) {
			ans[j][i+j] = max(ans[j][i+j], max(ans[j][i+j-1], ans[j+1][i+j]));
		}
	}
	cin >> q;
	/*
	if (q > 1) {
		return 0;
	}
	*/
	for (int i = 0;i < q;i++) {
		int l, r;
		cin >> l >> r;
		cout << ans[l][r] << "\n";	
	}
}
/*
5
5 2 1 5 3
1
1 5


5
5 4 4 5 4
1
1 5

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 0 ms 716 KB Output is correct
4 Correct 0 ms 716 KB Output is correct
5 Correct 0 ms 716 KB Output is correct
6 Correct 0 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 0 ms 716 KB Output is correct
4 Correct 0 ms 716 KB Output is correct
5 Correct 0 ms 716 KB Output is correct
6 Correct 0 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 359 ms 72568 KB Output is correct
12 Correct 381 ms 72564 KB Output is correct
13 Correct 406 ms 72528 KB Output is correct
14 Correct 391 ms 72584 KB Output is correct
15 Correct 365 ms 72724 KB Output is correct
16 Correct 405 ms 71924 KB Output is correct
17 Correct 362 ms 71928 KB Output is correct
18 Correct 373 ms 71880 KB Output is correct
19 Correct 361 ms 72460 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 716 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 332 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 0 ms 716 KB Output is correct
4 Correct 0 ms 716 KB Output is correct
5 Correct 0 ms 716 KB Output is correct
6 Correct 0 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 359 ms 72568 KB Output is correct
12 Correct 381 ms 72564 KB Output is correct
13 Correct 406 ms 72528 KB Output is correct
14 Correct 391 ms 72584 KB Output is correct
15 Correct 365 ms 72724 KB Output is correct
16 Correct 405 ms 71924 KB Output is correct
17 Correct 362 ms 71928 KB Output is correct
18 Correct 373 ms 71880 KB Output is correct
19 Correct 361 ms 72460 KB Output is correct
20 Runtime error 3 ms 716 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -