Submission #1096206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096206		Niosakaru	Triple Jump (JOI19_jumps)	C++17	5 / 100	4056 ms	10408 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5e5 + 5 , M = 5001;

long long n , p , q , rt , L[N] , R[N] , a[N] , dp[M][M] , Rt[M][M] , NRt[M][M];

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1 ; i <= n ; i ++) cin >> a[i];
    cin >> q;
    for (int i = 1 ; i <= q ; i ++) cin >> L[i] >> R[i];

    if (1LL * n * n * n / 6 * q <= 5e8){
        for (int i = 1 ; i <= q ; i ++){
            for (int l = L[i] ; l <= R[i] ; l ++){
                for (int mid = l + 1 ; mid <= R[i] ; mid ++){
                    for (int r = 2 * mid - l ; r <= R[i] ; r ++)
                        rt = max(rt,a[l] + a[mid] + a[r]);
                }
            }
            cout << rt << '\n';
            rt = 0;
        }
        return 0;
    }

    for (int i = 1 ; i <= n ; i ++){
        dp[i][i + 2] = i + 1;
        for (int j = i + 3 ; j <= n ; j ++){
            p = dp[i][j-1];
            for (int t = p ; t - i <= j - t ; t ++) if (a[t] + a[i] + a[j] >= a[i] + a[j] + a[p])
                p = t;
            dp[i][j] = p;
        }
        return 0;
    }

    for (int i = 1 ; i <= n ; i ++)
        for (int j = i + 2 ; j <= n ; j ++) Rt[i][j] = max(Rt[i][j - 1] , a[i] + a[j] + a[dp[i][j]]);

    for (int i = n ; i ; i --)
        for (int j = i - 2 ; j > 0 ; j --) NRt[j][i] = max(NRt[j+1][i] , a[i] + a[j] + a[dp[j][i]]);

    memset(dp , 0 , sizeof dp);
    for (int i = 1 ; i <= n ; i ++) for (int j = i + 2 ; j <= n ; j ++)
        dp[i][j] = max({dp[i][j-1],dp[i+1][j] , Rt[i][j] , NRt[i][j]});

    for (int i = 1 ; i <= q ; i ++){
        cout << dp[L[i]][R[i]] << '\n';
    }

    return 0;
}

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