Submission #914105

#TimeUsernameProblemLanguageResultExecution timeMemory
914105heavylightdecompTriple Jump (JOI19_jumps)C++14
19 / 100
382 ms237492 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...