oj.uz

Submission #1013007

# Submission time Handle Problem Language Result Execution time Memory
1013007 2024-07-03T05:09:21 Z Baytoro Triple Jump (JOI19_jumps) C++17
19 / 100
 2426 ms 79164 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[200'005*4];
int a[200'005];
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 sb2() {
    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;;
    }
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n<=5000) {
        sb2();
        return;
    }
    build(1,1,n);
    int q;cin>>q;
    while(q--) {
        int L,R;cin>>L>>R;
        int ans=0;
        int l=1,r=n;
        while(r-l>1) {
            int sum=a[l]+a[r]+query(l,(l+r)/2,1,1,n);
            ans=max(ans,sum);
            if(a[l]<a[r]) l++;
            else r--;
        }
        cout<<ans<<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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 2426 ms 79164 KB Output is correct
12 Correct 2239 ms 79008 KB Output is correct
13 Correct 2275 ms 78880 KB Output is correct
14 Correct 2340 ms 78944 KB Output is correct
15 Correct 2312 ms 78916 KB Output is correct
16 Correct 2322 ms 78364 KB Output is correct
17 Correct 2237 ms 78456 KB Output is correct
18 Correct 2254 ms 78404 KB Output is correct
19 Correct 2342 ms 79052 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 6224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2752 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 2 ms 2744 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 2426 ms 79164 KB Output is correct
12 Correct 2239 ms 79008 KB Output is correct
13 Correct 2275 ms 78880 KB Output is correct
14 Correct 2340 ms 78944 KB Output is correct
15 Correct 2312 ms 78916 KB Output is correct
16 Correct 2322 ms 78364 KB Output is correct
17 Correct 2237 ms 78456 KB Output is correct
18 Correct 2254 ms 78404 KB Output is correct
19 Correct 2342 ms 79052 KB Output is correct
20 Incorrect 79 ms 6224 KB Output isn't correct
21 Halted 0 ms 0 KB -