oj.uz

Submission #489472

# Submission time Handle Problem Language Result Execution time Memory
489472 2021-11-23T03:09:11 Z yungyao Triple Jump (JOI19_jumps) C++17
19 / 100
 1058 ms 77340 KB 
using namespace std;
#pragma GCC optimize ("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>

typedef long long LL;
typedef pair<int,int> pii;
#define iter(x) x.begin(),x.end()
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define REP(n) for (int __=n;__--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)

const int maxn = 5050,mod = 0;
const LL inf = 0;

int arr[maxn];
struct segmenttree{
    int mx[maxn*4];

    void maketree(int cur,int LB,int RB){
        if (LB == RB) mx[cur] = arr[LB];
        else{
            int m = (LB+RB)/2;

            maketree(cur*2,LB,m);
            maketree(cur*2+1,m+1,RB);
            mx[cur] = max(mx[cur*2], mx[cur*2+1]);
        }
    }

    int query(int l,int r,int cur,int LB,int RB){
        int m = (LB+RB)/2;
        if (l == LB and r == RB) return mx[cur];
        else if (r <= m) return query(l,r,cur*2,LB,m);
        else if (l > m) return query(l,r,cur*2+1,m+1,RB);
        else return max(query(l,m,cur*2,LB,m),query(m+1,r,cur*2+1,m+1,RB));
    }
}seg;

int ans[maxn][maxn];

void solve(){
    int n;

    cin >> n;
    REP1(i,n) cin >> arr[i];
    seg.maketree(1,1,n);
    REP1(i,n) for (int j=i+2;j<=n;++j){
        ans[i][j] = arr[i] + arr[j] + seg.query(i+1,(i+j)/2,1,1,n);
    }

    for (int i=n-3;i;--i) for (int j=i+3;j<=n;++j){
        ans[i][j] = max(ans[i][j],max(ans[i+1][j],ans[i][j-1]));
    }

    int q;
    cin >> q;
    while (q--){
        int l,r;

        cin >> l >> r;
        cout << ans[l][r] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1058 ms 76920 KB Output is correct
12 Correct 1046 ms 77156 KB Output is correct
13 Correct 1018 ms 77340 KB Output is correct
14 Correct 957 ms 77172 KB Output is correct
15 Correct 977 ms 77224 KB Output is correct
16 Correct 976 ms 76564 KB Output is correct
17 Correct 964 ms 76520 KB Output is correct
18 Correct 1004 ms 76464 KB Output is correct
19 Correct 993 ms 76856 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 412 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 204 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1058 ms 76920 KB Output is correct
12 Correct 1046 ms 77156 KB Output is correct
13 Correct 1018 ms 77340 KB Output is correct
14 Correct 957 ms 77172 KB Output is correct
15 Correct 977 ms 77224 KB Output is correct
16 Correct 976 ms 76564 KB Output is correct
17 Correct 964 ms 76520 KB Output is correct
18 Correct 1004 ms 76464 KB Output is correct
19 Correct 993 ms 76856 KB Output is correct
20 Runtime error 6 ms 412 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -