oj.uz

Submission #773594

# Submission time Handle Problem Language Result Execution time Memory
773594 2023-07-05T07:05:31 Z gagik_2007 Triple Jump (JOI19_jumps) C++17
19 / 100
 883 ms 356356 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
ll dp[N][N]; // l-ic r vor vercnenq maqsimumy
ll pf[N][N]; // l-ic enq sksum, kamayakan r'-i hamar minchev r
ll res[N][N]; // kamayakan l'-ic kamayakan r'
ll a[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("output.txt","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0;
    for(int l=n;l>=1;l--){
        for(int r=l+2;r<=n;r++){
            int mid=(l+r)/2;
            if(r==l+2)dp[l][r]=a[l]+a[r]+a[mid];
            else dp[l][r]=max(dp[l][r-1]-a[r-1]+a[r],a[l]+a[r]+a[mid]);

            pf[l][r]=max(pf[l][r-1],dp[l][r]);

            res[l][r]=max(res[l+1][r],pf[l][r]);

            ans=max(ans,res[l][r]);
        }
    }
    // for(int l=1;l<=n;l++){
    //     for(int r=l+2;r<=n;r++){
    //         cout<<dp[l][r]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int l=1;l<=n;l++){
    //     for(int r=l+2;r<=n;r++){
    //         cout<<pf[l][r]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    // for(int l=1;l<=n;l++){
    //     for(int r=l+2;r<=n;r++){
    //         cout<<res[l][r]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    cin>>m;
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        cout<<res[l][r]<<endl;
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 840 ms 356248 KB Output is correct
12 Correct 826 ms 356200 KB Output is correct
13 Correct 883 ms 356228 KB Output is correct
14 Correct 791 ms 356300 KB Output is correct
15 Correct 794 ms 356284 KB Output is correct
16 Correct 816 ms 355652 KB Output is correct
17 Correct 800 ms 355664 KB Output is correct
18 Correct 792 ms 355572 KB Output is correct
19 Correct 797 ms 356356 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 3540 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 340 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1620 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 840 ms 356248 KB Output is correct
12 Correct 826 ms 356200 KB Output is correct
13 Correct 883 ms 356228 KB Output is correct
14 Correct 791 ms 356300 KB Output is correct
15 Correct 794 ms 356284 KB Output is correct
16 Correct 816 ms 355652 KB Output is correct
17 Correct 800 ms 355664 KB Output is correct
18 Correct 792 ms 355572 KB Output is correct
19 Correct 797 ms 356356 KB Output is correct
20 Runtime error 29 ms 3540 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -