#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) ((int)x.size())
#define MAX 5007
int denseTable[MAX][MAX];
main(){ ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x];
for (int x = 0; x < n; x++){
int carry = arr[x];
for (int y = x; y < n; y++){
carry = max(arr[y], carry);
denseTable[x][y] = carry;
}
}
int results[n][n]; memset(results, 0, sizeof(results));
for (int a = 0; a < n; a++){
for (int c = a+2; c < n; c++){
int endpt = (a+c)/2;
results[a][c] = arr[a] + arr[c] + denseTable[a+1][endpt];
}
}
for (int sz = 1; sz <= n; sz++){
for (int x = 0; x+sz-1 < n; x++){
if (x+sz < n) results[x][x+sz] = max(results[x][x+sz], results[x][x+sz-1]);
if (x != 0) results[x-1][x+sz-1] = max(results[x-1][x+sz-1], results[x][x+sz-1]);
}
}
int q; cin >> q;
for (int x = 0; x < q; x++){
int ql, qr; cin >> ql >> qr; ql--; qr--;
cout << results[ql][qr] << '\n';
}
}
Compilation message
jumps.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
9 | main(){ ios_base::sync_with_stdio(0); cin.tie(0);
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4440 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4440 KB |
Output is correct |
11 |
Correct |
546 ms |
383872 KB |
Output is correct |
12 |
Correct |
442 ms |
392148 KB |
Output is correct |
13 |
Correct |
481 ms |
392240 KB |
Output is correct |
14 |
Correct |
456 ms |
392036 KB |
Output is correct |
15 |
Correct |
454 ms |
392068 KB |
Output is correct |
16 |
Correct |
467 ms |
391728 KB |
Output is correct |
17 |
Correct |
480 ms |
391572 KB |
Output is correct |
18 |
Correct |
466 ms |
391576 KB |
Output is correct |
19 |
Correct |
452 ms |
393828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1159 ms |
403480 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4440 KB |
Output is correct |
11 |
Correct |
546 ms |
383872 KB |
Output is correct |
12 |
Correct |
442 ms |
392148 KB |
Output is correct |
13 |
Correct |
481 ms |
392240 KB |
Output is correct |
14 |
Correct |
456 ms |
392036 KB |
Output is correct |
15 |
Correct |
454 ms |
392068 KB |
Output is correct |
16 |
Correct |
467 ms |
391728 KB |
Output is correct |
17 |
Correct |
480 ms |
391572 KB |
Output is correct |
18 |
Correct |
466 ms |
391576 KB |
Output is correct |
19 |
Correct |
452 ms |
393828 KB |
Output is correct |
20 |
Runtime error |
1159 ms |
403480 KB |
Execution killed with signal 11 |
21 |
Halted |
0 ms |
0 KB |
- |