oj.uz

Submission #914105

# Submission time Handle Problem Language Result Execution time Memory
914105 2024-01-21T05:31:13 Z heavylightdecomp Triple Jump (JOI19_jumps) C++14
19 / 100
 382 ms 237492 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 98392 KB Output is correct
2 Correct 16 ms 98396 KB Output is correct
3 Correct 16 ms 98396 KB Output is correct
4 Correct 17 ms 98396 KB Output is correct
5 Correct 16 ms 98520 KB Output is correct
6 Correct 18 ms 98396 KB Output is correct
7 Correct 18 ms 98396 KB Output is correct
8 Correct 18 ms 98508 KB Output is correct
9 Correct 17 ms 98396 KB Output is correct
10 Correct 17 ms 98420 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 98392 KB Output is correct
2 Correct 16 ms 98396 KB Output is correct
3 Correct 16 ms 98396 KB Output is correct
4 Correct 17 ms 98396 KB Output is correct
5 Correct 16 ms 98520 KB Output is correct
6 Correct 18 ms 98396 KB Output is correct
7 Correct 18 ms 98396 KB Output is correct
8 Correct 18 ms 98508 KB Output is correct
9 Correct 17 ms 98396 KB Output is correct
10 Correct 17 ms 98420 KB Output is correct
11 Correct 326 ms 109004 KB Output is correct
12 Correct 352 ms 108812 KB Output is correct
13 Correct 333 ms 108884 KB Output is correct
14 Correct 343 ms 109144 KB Output is correct
15 Correct 352 ms 108972 KB Output is correct
16 Correct 335 ms 107924 KB Output is correct
17 Correct 360 ms 108332 KB Output is correct
18 Correct 382 ms 108268 KB Output is correct
19 Correct 340 ms 108976 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 237492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 98392 KB Output is correct
2 Correct 16 ms 98396 KB Output is correct
3 Correct 16 ms 98396 KB Output is correct
4 Correct 17 ms 98396 KB Output is correct
5 Correct 16 ms 98520 KB Output is correct
6 Correct 18 ms 98396 KB Output is correct
7 Correct 18 ms 98396 KB Output is correct
8 Correct 18 ms 98508 KB Output is correct
9 Correct 17 ms 98396 KB Output is correct
10 Correct 17 ms 98420 KB Output is correct
11 Correct 326 ms 109004 KB Output is correct
12 Correct 352 ms 108812 KB Output is correct
13 Correct 333 ms 108884 KB Output is correct
14 Correct 343 ms 109144 KB Output is correct
15 Correct 352 ms 108972 KB Output is correct
16 Correct 335 ms 107924 KB Output is correct
17 Correct 360 ms 108332 KB Output is correct
18 Correct 382 ms 108268 KB Output is correct
19 Correct 340 ms 108976 KB Output is correct
20 Runtime error 147 ms 237492 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -