#include <bits/stdc++.h>
using namespace std;
const int N = (int) 5e5 + 7;
const int K = 19;
const int INF = (int) 1e9 + 7;
int n;
int q;
int a[N];
int lg[N];
int maxA[K][N];
int getMaxA(int l, int r) {
if (l > r) {
return -INF;
}
assert(1 <= l && l <= r && r <= n);
int k = lg[r - l + 1];
return max(maxA[k][l], maxA[k][r - (1 << k) + 1]);
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
//freopen ("input", "r", stdin);
cin >> n;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxA[0][i] = a[i];
}
for (int k = 1; (1 << k) <= n; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
maxA[k][i] = max(maxA[k - 1][i], maxA[k - 1][i + (1 << (k - 1))]);
}
}
cin >> q;
for (int iq = 1; iq <= q; iq++) {
int l, r, best = 0;
cin >> l >> r;
for (int i = l; i <= r; i++) {
for (int j = i + 1; j <= r; j++) {
int minK = 2 * j - i;
int maxK = r;
best = max(best, a[i] + a[j] + getMaxA(minK, maxK));
}
}
cout << best << "\n";
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Execution timed out |
4051 ms |
912 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
4091 ms |
14964 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
320 KB |
Output is correct |
9 |
Correct |
1 ms |
316 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Execution timed out |
4051 ms |
912 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |