Submission #1096205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096205		Niosakaru	Triple Jump (JOI19_jumps)	C++14	5 / 100	4014 ms	12888 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;

unsigned int 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;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:15:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   15 |     for (int i = 1 ; i <= n ; i ++) cin >> a[i];
      |                      ~~^~~~
jumps.cpp:17:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   17 |     for (int i = 1 ; i <= q ; i ++) cin >> L[i] >> R[i];
      |                      ~~^~~~
jumps.cpp:20:28: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   20 |         for (int i = 1 ; i <= q ; i ++){
      |                          ~~^~~~
jumps.cpp:21:35: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   21 |             for (int l = L[i] ; l <= R[i] ; l ++){
      |                                 ~~^~~~~~~
jumps.cpp:22:44: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   22 |                 for (int mid = l + 1 ; mid <= R[i] ; mid ++){
      |                                        ~~~~^~~~~~~
jumps.cpp:23:50: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   23 |                     for (int r = 2 * mid - l ; r <= R[i] ; r ++)
      |                                                ~~^~~~~~~
jumps.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   33 |     for (int i = 1 ; i <= n ; i ++){
      |                      ~~^~~~
jumps.cpp:35:32: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   35 |         for (int j = i + 3 ; j <= n ; j ++){
      |                              ~~^~~~
jumps.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   44 |     for (int i = 1 ; i <= n ; i ++)
      |                      ~~^~~~
jumps.cpp:45:32: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   45 |         for (int j = i + 2 ; j <= n ; j ++) Rt[i][j] = max(Rt[i][j - 1] , a[i] + a[j] + a[dp[i][j]]);
      |                              ~~^~~~
jumps.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   51 |     for (int i = 1 ; i <= n ; i ++) for (int j = i + 2 ; j <= n ; j ++)
      |                      ~~^~~~
jumps.cpp:51:60: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   51 |     for (int i = 1 ; i <= n ; i ++) for (int j = i + 2 ; j <= n ; j ++)
      |                                                          ~~^~~~
jumps.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
   54 |     for (int i = 1 ; i <= q ; i ++){
      |                      ~~^~~~

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