oj.uz

Submission #615326

# Submission time Handle Problem Language Result Execution time Memory
615326 2022-07-31T08:25:59 Z AbdelmagedNour Triple Jump (JOI19_jumps) C++17
19 / 100
 353 ms 77192 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int sp[13][N],dp[N][N];
void build(int n){
    for(int j=1;j<13;j++){
        for(int i=0;i+(1<<j)<=n;i++){
            sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
        }
    }
}
int RMQ(int l,int r){
    int sz=__lg(r-l+1);
    return max(sp[sz][l],sp[sz][r-(1<<sz)+1]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>sp[0][i];
    build(n);
    for(int sz=2;sz<n;sz++){
        for(int i=0;i+sz<n;i++){
            dp[i][i+sz]=sp[0][i]+sp[0][i+sz]+RMQ(i+1,(i+sz+i)/2);
            dp[i][i+sz]=max({dp[i][i+sz],dp[i+1][i+sz],dp[i][i+sz-1]});
        }
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        cout<<dp[l][r]<<"\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 736 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 736 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 315 ms 77192 KB Output is correct
12 Correct 318 ms 77092 KB Output is correct
13 Correct 310 ms 77192 KB Output is correct
14 Correct 352 ms 77132 KB Output is correct
15 Correct 334 ms 77188 KB Output is correct
16 Correct 340 ms 76548 KB Output is correct
17 Correct 339 ms 76520 KB Output is correct
18 Correct 319 ms 76452 KB Output is correct
19 Correct 353 ms 76992 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1748 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 1 ms 340 KB Output is correct
2 Correct 1 ms 736 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 315 ms 77192 KB Output is correct
12 Correct 318 ms 77092 KB Output is correct
13 Correct 310 ms 77192 KB Output is correct
14 Correct 352 ms 77132 KB Output is correct
15 Correct 334 ms 77188 KB Output is correct
16 Correct 340 ms 76548 KB Output is correct
17 Correct 339 ms 76520 KB Output is correct
18 Correct 319 ms 76452 KB Output is correct
19 Correct 353 ms 76992 KB Output is correct
20 Runtime error 9 ms 1748 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -