oj.uz

Submission #489462

# Submission time Handle Problem Language Result Execution time Memory
489462 2021-11-23T02:57:12 Z Haruto810198 Triple Jump (JOI19_jumps) C++17
19 / 100
 428 ms 127784 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

const int MAX = 5010;

int n, q;
int arr[MAX];
int st[MAX][20];
int res[MAX][MAX];

int query(int l, int r){
	int rk = __lg(r - l + 1);
	return max(st[l][rk], st[r - (1<<rk) + 1][rk]);
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 1, n, 1){
		cin>>arr[i];
	}
	
	FOR(i, 1, n, 1){
		st[i][0] = arr[i];
	}
	FOR(j, 1, 19, 1){
		FOR(i, 1, n, 1){
			int ii = i + (1<<(j - 1));
			if(ii <= n) st[i][j] = max(st[i][j - 1], st[ii][j - 1]);
			else st[i][j] = st[i][j - 1];
		}
	}
	
	FOR(i, 1, n, 1){
		FOR(k, i + 2, n, 1){
			int j = (i + k) / 2;
			res[i][k] = arr[i] + query(i + 1, j) + arr[k];
		}
	}
	
	FOR(dis, 3, n - 1, 1){
		FOR(i, 1, n - dis, 1){
			int j = i + dis;
			res[i][j] = max({res[i][j], res[i + 1][j], res[i][j - 1]});
			//cerr<<"res["<<i<<"]["<<j<<"] = "<<res[i][j]<<endl;
		}
	}
	
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		cout<<res[l][r]<<'\n';
	}
	
	return 0;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 716 KB Output is correct
5 Correct 1 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 0 ms 716 KB Output is correct
9 Correct 1 ms 700 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 0 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 1 ms 716 KB Output is correct
5 Correct 1 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 0 ms 716 KB Output is correct
9 Correct 1 ms 700 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 375 ms 127492 KB Output is correct
12 Correct 398 ms 127784 KB Output is correct
13 Correct 371 ms 127748 KB Output is correct
14 Correct 375 ms 127776 KB Output is correct
15 Correct 378 ms 127768 KB Output is correct
16 Correct 389 ms 127096 KB Output is correct
17 Correct 382 ms 127108 KB Output is correct
18 Correct 380 ms 127044 KB Output is correct
19 Correct 428 ms 127656 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 500 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 0 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 1 ms 716 KB Output is correct
5 Correct 1 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 0 ms 716 KB Output is correct
9 Correct 1 ms 700 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 375 ms 127492 KB Output is correct
12 Correct 398 ms 127784 KB Output is correct
13 Correct 371 ms 127748 KB Output is correct
14 Correct 375 ms 127776 KB Output is correct
15 Correct 378 ms 127768 KB Output is correct
16 Correct 389 ms 127096 KB Output is correct
17 Correct 382 ms 127108 KB Output is correct
18 Correct 380 ms 127044 KB Output is correct
19 Correct 428 ms 127656 KB Output is correct
20 Runtime error 4 ms 500 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -