Submission #1145648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145648		keisuke6	Triple Jump (JOI19_jumps)	C++20	0 / 100	707 ms	5140 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    srand((unsigned)time(NULL));
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int N;
    cin>>N;
    vector<int> A(N);
    vector<pair<int,int>> S(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
        S[i] = {A[i],i};
    }
    sort(S.rbegin(),S.rend());
    int ans = 0;
    for(int i=0;i<500;i++){
        int a,t;
        tie(a,t) = S[i];
        int cl = clock();
        {
            int ma = 0;
            for(int i=t+2;i<N;i++){
                if((i-t)%2 == 0) ma = max(ma,A[(i+t)/2]);
                ans = max(ans,a+ma+A[i]);
            }
        }
        {
            int ind = N-1, ma = -1e18;
            for(int i=0;i<t;i++){
                while(t-i <= ind-t){
                    ma = max(ma,A[ind]);
                    ind--;
                }
                ans = max(ans,A[i]+A[t]+ma);
            }
        }
    }
    for(int i=500;i<1000;i++){
        int a,t;
        tie(a,t) = S[i];
        int cl = clock();
        {
            int ma = 0;
            for(int i=t+2;i<N;i++){
                if((i-t)%2 == 0) ma = max(ma,A[(i+t)/2]);
                ans = max(ans,a+ma+A[i]);
            }
        }
        {
            int ind = N-1, ma = -1e18;
            for(int i=0;i<t;i++){
                while(t-i <= ind-t){
                    ma = max(ma,A[ind]);
                    ind--;
                }
                ans = max(ans,A[i]+A[t]+ma);
            }
        }
    }
    for(int l=0;l<N-2;l++){
        int ma = 0;
        for(int r=l+2;r<=min(N-1,l+2000);r++){
            if((r-l)^1) ma = max(ma,A[(l+r)/2]);
            ans = max(ans,ma+A[l]+A[r]);
        }
    }
    cout<<ans<<endl;
}

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