제출 #914105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
914105		heavylightdecomp	3단 점프 (JOI19_jumps)	C++14	19 / 100	382 ms	237492 KiB

jumps

#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';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54