제출 #1096988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096988		Tame	3단 점프 (JOI19_jumps)	C++14	19 / 100	346 ms	147144 KiB

jumps

#include <bits/stdc++.h>
#define pu push
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el cout<<"\n"
#define ll long long
#define ld long double
#define MASK(i) (1LL<<(i))
#define BIT(x, i) (((x)>>(i))&1)
#define SET_ON(x, i) ((x)|MASK(i))
#define SET_OFF(x, i) ((x)&~MASK(i))
#define c_bit(i) __builtin_popcount(i)
const int MAX_SIZE = 500010;
const int inf = (int)1e9+7;
const ll INF = (ll)1e18;
using namespace std;

template<class T1, class T2>
    bool maximize(T1 &x, T2 y){if(x<y){x=y; return true;} return false;}
template<class T1, class T2>
    bool minimize(T1 &x, T2 y){if(x>y){x=y; return true;} return false;}

int nLength, nQuery;
int a[MAX_SIZE];

vector<pair<int,int>>queries, tmp;

struct SegmentTree{
    int n; vector<pair<int,int>>st;
    SegmentTree(int _n=0){
        n=_n; st.resize(4*n+5);
    }
    void build(int id, int l, int r){
        if (l==r){
            st[id]=make_pair(a[l], l); return;
        }
        int m = (l+r)>>1;
        build(2*id,l,m); build(2*id+1,m+1,r);
        st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
        st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
    }
    void update(int id, int l, int r, int v, int k){
        if (r<v || v<l) return;
        if (l==r){
            st[id].fi=k; return;
        }
        int m = (l+r)>>1;
        update(2*id, l, m, v, k); update(2*id+1, m+1, r, v, k);
        st[id].fi = max(st[2*id].fi, st[2*id+1].fi);
        st[id].se = (st[2*id].fi>st[2*id+1].fi)?(st[2*id].se):(st[2*id+1].se);
    }
    pair<int,int>get(int id, int l, int r, int u, int v){
        if (r<u || v<l){
            pair<int,int>e = make_pair(-inf, -inf);
            return e;
        }
        if (l>=u && r<=v) return st[id];
        int m = (l+r)>>1;
        pair<int,int>x=get(2*id, l, m, u, v), y=get(2*id+1, m+1, r, u, v);
        if (x.fi > y.fi) return x;
        return y;
    }
};
SegmentTree IT(MAX_SIZE);

void init(){
    cin>>nLength;
    for (int i=1; i<=nLength; i++){
        cin>>a[i];
    }
    cin>>nQuery;
    for (int i=1; i<=nQuery; i++){
        int l, r; cin>>l>>r;
        queries.pb(make_pair(l, r));
    }
}

bool cmp(const pair<int,int>&x, pair<int,int>&y){
    return x.se < y.se;
}

namespace subtask1{
    bool check(){
        return max(nLength, nQuery)<=100;
    }

    ll board[105][105];

    void solve(){
        memset(board, -0x3f, sizeof(board));
        for (int i=1; i<=nLength; i++){
            for (int j=i+1; j<=nLength; j++){
                for (int k=i+1; k<j; k++){
                    if (abs(k-i) <= abs(j-k)) maximize(board[i][j], a[i]+a[j]+a[k]);
                }
            }
        }
        for (int i=0; i<(int)queries.size(); i++){
            int l=queries[i].fi, r=queries[i].se; ll ans=0;
            for (int u=l; u<=r; u++){
                for (int v=u; v<=r; v++){
                    maximize(ans, board[u][v]);
                }
            }
            cout<<ans<<"\n";
        }
    }
}

namespace subtask2{
    bool check(){
        return nLength<=5000;
    }

    int rmq[5010][15], LOG=13;
    ll dp[5003][5003];

    int getMax(int l, int r){
        int k = 31 - __builtin_clz(r-l+1);
        return max(rmq[l][k], rmq[r-MASK(k)+1][k]);
    }

    void solve(){
        for (int i=1; i<=nLength; i++) rmq[i][0] = a[i];
        for (int j=1; j<=LOG; j++){
            for (int i=1; i<=nLength; i++){
                rmq[i][j] = max(rmq[i][j-1], rmq[i+MASK(j-1)][j-1]);
            }
        }

        for (int i=1; i<=nLength; i++){
            for (int j=i+2; j<=nLength; j++){
                maximize(dp[i][j], a[i] + a[j] + getMax(i+1, (i+j)/2));
            }
        }

        for (int j=1; j<=nLength; j++){
            for (int i=j; i>=1; i--){
                if (i+1<j) maximize(dp[i][j], dp[i+1][j]);
                if (j-1>i) maximize(dp[i][j], dp[i][j-1]);
                if (i+1<j && j-1>i) maximize(dp[i][j], dp[i+1][j-1]);
            }
        }

        for (int i=0; i<(int)queries.size(); i++){
            int l=queries[i].fi, r=queries[i].se;
            cout<<dp[l][r]<<"\n";
        }
    }
}

void ilovesunshine(){
    init();

    if (subtask1::check()) return subtask1::solve();
    if (subtask2::check()) return subtask2::solve();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ilovesunshine();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54