oj.uz

Submission #1096451

# Submission time Handle Problem Language Result Execution time Memory
1096451 2024-10-04T13:16:46 Z ducdev Triple Jump (JOI19_jumps) C++14
19 / 100
 277 ms 244124 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int MXN = 5e3;

int n , q;
ll a[MXN + 5] , maxVals[MXN + 5][MXN + 5];
ll dp[MXN + 5][MXN + 5];

void precompute(){
    for (int i = 1; i <= n ;i++){
        for (int j = i; j <= n ;j++){
            maxVals[i][j] = max(maxVals[i][j - 1] , a[j]);
        }
    }

    for (int l = n - 2;l >= 1; l--){
        for (int r = l + 2 ; r <= n ;r++){
            dp[l][r] = max({dp[l + 1][r] , dp[l][r - 1] , a[l] + a[r] + maxVals[l + 1][(r + l) / 2]});
        }
    }
}

signed main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i<= n ;i++) cin >> a[i];
    precompute();
    cin >> q;
    while(q--){
        int l , r; cin >> l >> r;
        cout << dp[l][r] <<'\n';
     }
}
//aaca
//aaac

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 264 ms 244124 KB Output is correct
12 Correct 277 ms 243856 KB Output is correct
13 Correct 256 ms 244028 KB Output is correct
14 Correct 259 ms 243928 KB Output is correct
15 Correct 268 ms 243928 KB Output is correct
16 Correct 239 ms 243440 KB Output is correct
17 Correct 238 ms 243416 KB Output is correct
18 Correct 242 ms 243280 KB Output is correct
19 Correct 248 ms 243980 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 264 ms 244124 KB Output is correct
12 Correct 277 ms 243856 KB Output is correct
13 Correct 256 ms 244028 KB Output is correct
14 Correct 259 ms 243928 KB Output is correct
15 Correct 268 ms 243928 KB Output is correct
16 Correct 239 ms 243440 KB Output is correct
17 Correct 238 ms 243416 KB Output is correct
18 Correct 242 ms 243280 KB Output is correct
19 Correct 248 ms 243980 KB Output is correct
20 Runtime error 6 ms 600 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -