oj.uz

Submission #1012999

# Submission time Handle Problem Language Result Execution time Memory
1012999 2024-07-03T04:34:15 Z Baytoro Triple Jump (JOI19_jumps) C++17
19 / 100
 2445 ms 77136 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
//#define int ll
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
int n,m;
const int N=1e5+5;
int dp[5005][5005];
int tree[5005*4];
int a[5005];
void build(int x, int l, int r) {
    if(l==r) {
        tree[x]=a[l];
        return;
    }
    int md=(l+r)/2;

    build(2*x,l,md);
    build(2*x+1,md+1,r);

    tree[x]=max(tree[2*x],tree[2*x+1]);
}

int query(int lx, int rx, int x, int l, int r) {
    if(l>rx || r<lx) return 0;
    if(lx<=l && r<=rx) return tree[x];

    int md=(l+r)/2;

    return max(query(lx,rx,2*x,l,md),query(lx,rx,2*x+1,md+1,r));
}
void solve() {
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int j=2;j<=n;j++){
        for(int i=1;i<=n;i++) {
            if(i+j>n) break;

            dp[i][i+j]=a[i]+a[i+j]+query(i+1,(i+i+j)/2,1,1,n);

            dp[i][i+j]=max({dp[i][i+j],dp[i+1][i+j],dp[i][i+j-1]});
            //cout<<i<<' '<<i+j<<' '<<dp[i][i+j]<<endl;

        }
    }
    int q;cin>>q;
    while(q--) {
        int l,r;cin>>l>>r;
        cout<<dp[l][r]<<endl;;
    }
}
signed main(){
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}
//#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2365 ms 76956 KB Output is correct
12 Correct 2125 ms 77044 KB Output is correct
13 Correct 2222 ms 77136 KB Output is correct
14 Correct 2383 ms 77096 KB Output is correct
15 Correct 2428 ms 77136 KB Output is correct
16 Correct 2376 ms 76468 KB Output is correct
17 Correct 2445 ms 76484 KB Output is correct
18 Correct 2260 ms 76368 KB Output is correct
19 Correct 2313 ms 76920 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 46164 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 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2365 ms 76956 KB Output is correct
12 Correct 2125 ms 77044 KB Output is correct
13 Correct 2222 ms 77136 KB Output is correct
14 Correct 2383 ms 77096 KB Output is correct
15 Correct 2428 ms 77136 KB Output is correct
16 Correct 2376 ms 76468 KB Output is correct
17 Correct 2445 ms 76484 KB Output is correct
18 Correct 2260 ms 76368 KB Output is correct
19 Correct 2313 ms 76920 KB Output is correct
20 Runtime error 80 ms 46164 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -