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>
using namespace std;
#define cerr while(0) cerr
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x = x;cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define i32 int32_t
const int INF = 1e9;
//DP[L][R] = precomputed answer for L,R
//= max(DP[L+1][R], DP[L][R-1], take both L,R)
// -> RMQ(L+1, (L+R)/2)
//0-index for rmq, 1-index everything else
struct rmq {
//MUST USE 32-BIT integers
const static i32 lg = 20;
vt<vt<i32>> haha;
rmq() {}
rmq(vt<i32> ar) {
haha.pb(ar);
//[i, i + 1 << k)
f0r(k,1,lg+1) { //lg+1 very important
haha.pb(vt<i32> (sz(ar)));
f0r(i,0,sz(ar)) {
//BUG: [k][i] not [i][k]
//BUG: order of operations
haha[k][i] = max(haha[k-1][i], haha[k-1][min(sz(ar)-1,i+(1<<(k-1)))]);
}
}
}
i32 query(i32 l, i32 r) {
//BUG: dep is supposed to be 31 because of signed integer
i32 dep = 31 - __builtin_clz(r-l);
int what_rmq = max(haha[dep][l], haha[dep][r-(1<<dep)+1]);
debug(l) debug(r) debug(dep) debug(what_rmq);
// assert(l <= r-(1<<dep));
return max(haha[dep][l], haha[dep][r-(1<<dep)+1]);
}
};
const int maxn = 5005;
int dp[maxn][maxn], ar[maxn], N,Q;
rmq lol;
int rec(int L, int R) {
assert(R-L >= 2);
if(R-L == 2) return ar[L] + ar[L+1] + ar[L+2];
if(dp[L][R] != -1) return dp[L][R];
int res = -INF;
res = max({res, rec(L+1,R), rec(L,R-1), ar[L] + ar[R] + lol.query(L+1, (L+R)/2)});
debug(L) debug(R) debug(res)
return dp[L][R] = res;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
memset(dp, -1, sizeof dp);
cin >> N;
vt<int> feed = {-INF};
f0r(i,1,N+1) cin >> ar[i], feed.pb(ar[i]);
lol = rmq(feed);
cin >> Q;
f0r(_,0,Q) {
int L,R; cin >> L >> R;
int res = rec(L,R);
cout << res << '\n';
}
}
# | 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... |