oj.uz

Submission #489488

# Submission time Handle Problem Language Result Execution time Memory
489488 2021-11-23T03:46:49 Z fhvirus Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 124304 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int, int> pii;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I> bool chmin(I&a, I b){ return a > b ? (a=b, true) : false; }
template<class I> bool chmax(I&a, I b){ return a < b ? (a=b, true) : false; }
#ifdef OWO
#define debug(args...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template<class I> void LKJ(I&&x){ cerr << x << endl; }
template<class I, class...T> void LKJ(I&&x, T&&...t){ cerr << x << ", "; LKJ(t...); }
template<class I> void OI(I a, I b){ while(a < b) cerr << *a << " \n"[next(a) == b], ++a; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

const int kL = 20;
const int kN = 500005;
const int kQ = 500005;
int N, Q, A[kN];
int L[kQ], R[kQ];

void input(){
	cin >> N;
	for(int i = 1; i <= N; ++i)
		cin >> A[i];
	cin >> Q;
	for(int i = 0; i < Q; ++i)
		cin >> L[i] >> R[i];
}

int sp[kL][kN];
void init(){
	for(int i = 1; i <= N; ++i)
		sp[0][i] = A[i];
	for(int l = 1; l < kL; ++l)
		for(int i = 1; i <= N; ++i)
			sp[l][i] = max(sp[l-1][i], sp[l-1][i+(1<<(l-1))]);
}
int query(int l, int r){
	int d = __lg(r-l+1);
	return max(sp[d][l], sp[d][r-(1<<d)+1]);
}


int ans[5005][5005];
void solve(){
	init();
	for(int i = 1; i <= N; ++i){
		for(int j = i+2; j <= N; ++j){
			ans[i][j] = A[i] + A[j] + query(i+1, i+(j-i)/2);
		}
	}
	for(int i = 1; i <= N; ++i)
		for(int j = i+2; j <= N; ++j)
			ans[i][j] = max(ans[i][j], ans[i][j-1]);

	for(int i = N-1; i >= 1; --i)
		for(int j = i+2; j <= N; ++j)
			ans[i][j] = max(ans[i][j], ans[i+1][j]);

	for(int i = 0; i < Q; ++i)
		cout << ans[L[i]][R[i]] << '\n';
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	input();
	solve();
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 292 ms 76660 KB Output is correct
12 Correct 285 ms 76612 KB Output is correct
13 Correct 292 ms 76708 KB Output is correct
14 Correct 270 ms 76680 KB Output is correct
15 Correct 272 ms 76708 KB Output is correct
16 Correct 300 ms 75976 KB Output is correct
17 Correct 301 ms 76068 KB Output is correct
18 Correct 302 ms 76012 KB Output is correct
19 Correct 318 ms 76612 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4066 ms 124304 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 844 KB Output is correct
6 Correct 1 ms 844 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 KB Output is correct
11 Correct 292 ms 76660 KB Output is correct
12 Correct 285 ms 76612 KB Output is correct
13 Correct 292 ms 76708 KB Output is correct
14 Correct 270 ms 76680 KB Output is correct
15 Correct 272 ms 76708 KB Output is correct
16 Correct 300 ms 75976 KB Output is correct
17 Correct 301 ms 76068 KB Output is correct
18 Correct 302 ms 76012 KB Output is correct
19 Correct 318 ms 76612 KB Output is correct
20 Execution timed out 4066 ms 124304 KB Time limit exceeded
21 Halted 0 ms 0 KB -