oj.uz

Submission #771084

# Submission time Handle Problem Language Result Execution time Memory
771084 2023-07-02T12:33:25 Z Dan4Life Triple Jump (JOI19_jumps) C++17
19 / 100
 882 ms 77056 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)5e3+10;
int a[mxN], dp[mxN][mxN];
 
int main(){
	int n, q; cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> q;
	for(int i = 1; i <= n; i++){
		int k = i+1, mx = 0;
		for(int j = i+2; j <= n; j++){
			while(2*k<=i+j) mx = max(mx,a[k++]);
			dp[i][j]=mx+a[i]+a[j];
		}
	}
	for(int l = 1; l <= n; l++){
		for(int i=1,j=i+l-1; j<= n; i++,j++){
			dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
			dp[i-1][j] = max(dp[i-1][j],dp[i][j]);
		}
	}
	while(q--){
		int l, r; cin >> l>> r;
		cout <<dp[l][r] << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 1 ms 688 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 1 ms 688 KB Output is correct
11 Correct 868 ms 77056 KB Output is correct
12 Correct 866 ms 76896 KB Output is correct
13 Correct 869 ms 76928 KB Output is correct
14 Correct 879 ms 76928 KB Output is correct
15 Correct 881 ms 77040 KB Output is correct
16 Correct 878 ms 76308 KB Output is correct
17 Correct 863 ms 76236 KB Output is correct
18 Correct 882 ms 76372 KB Output is correct
19 Correct 873 ms 76896 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 596 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 212 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 692 KB Output is correct
10 Correct 1 ms 688 KB Output is correct
11 Correct 868 ms 77056 KB Output is correct
12 Correct 866 ms 76896 KB Output is correct
13 Correct 869 ms 76928 KB Output is correct
14 Correct 879 ms 76928 KB Output is correct
15 Correct 881 ms 77040 KB Output is correct
16 Correct 878 ms 76308 KB Output is correct
17 Correct 863 ms 76236 KB Output is correct
18 Correct 882 ms 76372 KB Output is correct
19 Correct 873 ms 76896 KB Output is correct
20 Runtime error 4 ms 596 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -