oj.uz

Submission #854929

# Submission time Handle Problem Language Result Execution time Memory
854929 2023-09-29T12:11:24 Z vjudge1 Triple Jump (JOI19_jumps) C++17
19 / 100
 395 ms 283812 KB 
#include<bits/stdc++.h>
using namespace std; 
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7;
const int N = 5010;
const ll inf = 1e18;
int mx[N][N];
int suf[N];
int a[N];
int ans[N][N];
int dp[N][N];
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		mx[i][i] = a[i];
	}
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			mx[i][j] = max(mx[i][j-1], mx[i][j]);
		}
	}
	for (int i=1;i<=n;i++){
		dp[i][i+1] = a[i]+a[i+1];
	}
	for (int i=1;i<=n;i++){
		for (int j=i+2;j<=n;j++){
			dp[i][j] = max(dp[i][j-1], a[j]+mx[i][j-1]);
		}
	}
	memset(mx, 0, sizeof(mx));
	for (int l=1;l<=n-1;l++){
		for (int r=l+1;r<=n;r++){
			int c = r + (r-l);
			if (c>n) break;
			suf[c] = max(dp[l][r], suf[c]);
		}
		for (int i=1;i<=n;i++){
			suf[i] = max(suf[i], suf[i-1]);
		}
		for (int r=l+2;r<=n;r++){
			ans[l][r] = max(ans[l][r-1], suf[r]+a[r]);
		}
		memset(suf, 0, sizeof(suf));
	}
	for (int i=1;i<=n;i++){
		for (int j=i;j>=1;j--){
			ans[j][i] = max(ans[j+1][i], ans[j][i]);
		}
	}
	int q;
	cin >> q;
	while (q--){
		int l, r;
		cin >> l >> r;
		cout << ans[l][r] << endl;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 99928 KB Output is correct
2 Correct 12 ms 102492 KB Output is correct
3 Correct 12 ms 102492 KB Output is correct
4 Correct 12 ms 102416 KB Output is correct
5 Correct 12 ms 102492 KB Output is correct
6 Correct 12 ms 102492 KB Output is correct
7 Correct 12 ms 102492 KB Output is correct
8 Correct 12 ms 102488 KB Output is correct
9 Correct 13 ms 102492 KB Output is correct
10 Correct 12 ms 102492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 99928 KB Output is correct
2 Correct 12 ms 102492 KB Output is correct
3 Correct 12 ms 102492 KB Output is correct
4 Correct 12 ms 102416 KB Output is correct
5 Correct 12 ms 102492 KB Output is correct
6 Correct 12 ms 102492 KB Output is correct
7 Correct 12 ms 102492 KB Output is correct
8 Correct 12 ms 102488 KB Output is correct
9 Correct 13 ms 102492 KB Output is correct
10 Correct 12 ms 102492 KB Output is correct
11 Correct 393 ms 283812 KB Output is correct
12 Correct 382 ms 283672 KB Output is correct
13 Correct 380 ms 283552 KB Output is correct
14 Correct 394 ms 283808 KB Output is correct
15 Correct 383 ms 283680 KB Output is correct
16 Correct 395 ms 282940 KB Output is correct
17 Correct 394 ms 282900 KB Output is correct
18 Correct 390 ms 283004 KB Output is correct
19 Correct 377 ms 283700 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 102 ms 200700 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 12 ms 99928 KB Output is correct
2 Correct 12 ms 102492 KB Output is correct
3 Correct 12 ms 102492 KB Output is correct
4 Correct 12 ms 102416 KB Output is correct
5 Correct 12 ms 102492 KB Output is correct
6 Correct 12 ms 102492 KB Output is correct
7 Correct 12 ms 102492 KB Output is correct
8 Correct 12 ms 102488 KB Output is correct
9 Correct 13 ms 102492 KB Output is correct
10 Correct 12 ms 102492 KB Output is correct
11 Correct 393 ms 283812 KB Output is correct
12 Correct 382 ms 283672 KB Output is correct
13 Correct 380 ms 283552 KB Output is correct
14 Correct 394 ms 283808 KB Output is correct
15 Correct 383 ms 283680 KB Output is correct
16 Correct 395 ms 282940 KB Output is correct
17 Correct 394 ms 282900 KB Output is correct
18 Correct 390 ms 283004 KB Output is correct
19 Correct 377 ms 283700 KB Output is correct
20 Runtime error 102 ms 200700 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -