oj.uz

Submission #1096206

# Submission time Handle Problem Language Result Execution time Memory
1096206 2024-10-04T05:42:06 Z Niosakaru Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 10408 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6740 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6740 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Incorrect 54 ms 10408 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4056 ms 7440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6740 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Incorrect 54 ms 10408 KB Output isn't correct
12 Halted 0 ms 0 KB -