This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define FILE
#define fr first
#define se second
using namespace std;
const long long M = 21;
const long long N = 5e3 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;
int n;
int q;
int a[N];
int lg[N];
int d[N][M];
int ans[N][N];
int get(int l, int r){
if(l > r){
return 0;
}
int h = (r - l + 1);
return max(d[l][lg[h]], d[r - (1 << lg[h]) + 1][lg[h]]);
}
int main()
{
#ifdef FILEs
freopen("input.txt", "r", stdin);
/// freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
d[i][0] = a[i];
}
lg[2] = 1;
for(int i = 3; i < N; i ++){
lg[i] = lg[i / 2] + 1;
}
for(int j = 1; j < M; j ++){
for(int i = 1; i + (1 << j) - 1 <= n; i ++){
d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
}
for(int l = 2; l < n; l ++){
/// cout << "length: " << l << ":\n";
for(int i = 1; i + l <= n; i ++){
/// cout << "\t" << i << " (" << i + 1 << ", " << (2 * i + l) / 2 << ") " << i + l << "\n";
/// cout << "\t" << a[i] << " " << get(i + 1, (2 * i + l) / 2) << " " << a[i + l] << "\n";
ans[i][l] = max(ans[i][l - 1], a[i] + a[i + l] + get(i + 1, (2 * i + l)/ 2));
}
}
for(int l = 2; l < n; l ++){
for(int i = 1; i + l <= n; i ++){
ans[i][l] = max(ans[i][l], ans[i + 1][l - 1]);
}
}
cin >> q;
while(q --){
int l, r;
int mx = 0;
cin >> l >> r;
assert(r - l + 1 >= 3);
cout << ans[l][r - l] << "\n";
}
}
Compilation message (stderr)
jumps.cpp: In function 'int main()':
jumps.cpp:66:13: warning: unused variable 'mx' [-Wunused-variable]
int mx = 0;
^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |