Submission #489472

#	Time	Username	Problem	Language	Result	Execution time	Memory
489472		yungyao	Triple Jump (JOI19_jumps)	C++17	19 / 100	1058 ms	77340 KiB

jumps

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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54