oj.uz

Submission #433786

# Submission time Handle Problem Language Result Execution time Memory
433786 2021-06-20T10:50:32 Z dxz05 Triple Jump (JOI19_jumps) C++14
19 / 100
 4000 ms 204384 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 5050;

#define MP make_pair
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int mx[N][N], ans[N][N];
int a[N];

void solve(){
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for (int l = 1; l <= n; l++){
        for (int r = l; r <= n; r++){
            mx[l][r] = max(mx[l][r - 1], a[r]);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j = i + 2; j <= n; j++){
            int k = (i + j) / 2;
            ans[i][j] = a[i] + a[j] + mx[i + 1][k];
        }
    }

    for (int i = n; i >= 1; i--){
        for (int j = i; j <= n; j++){
            ans[i][j] = max({ans[i][j], ans[i + 1][j], ans[i][j - 1]});
        }
    }

    int q;
    cin >> q;

    while (q--){
        int l, r;
        cin >> l >> r;
        cout << ans[l][r] << endl;
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("output.txt", "w", stdout);
    int tests = 1;
   // cin >> tests;

    while (tests--){
        solve();
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 2 ms 1148 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 2 ms 1148 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1213 ms 144384 KB Output is correct
12 Correct 1267 ms 144276 KB Output is correct
13 Correct 1279 ms 144312 KB Output is correct
14 Correct 1239 ms 144348 KB Output is correct
15 Correct 1239 ms 144360 KB Output is correct
16 Correct 1174 ms 143640 KB Output is correct
17 Correct 1179 ms 143624 KB Output is correct
18 Correct 1140 ms 143708 KB Output is correct
19 Correct 1166 ms 144304 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 204384 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 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 2 ms 1148 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1213 ms 144384 KB Output is correct
12 Correct 1267 ms 144276 KB Output is correct
13 Correct 1279 ms 144312 KB Output is correct
14 Correct 1239 ms 144348 KB Output is correct
15 Correct 1239 ms 144360 KB Output is correct
16 Correct 1174 ms 143640 KB Output is correct
17 Correct 1179 ms 143624 KB Output is correct
18 Correct 1140 ms 143708 KB Output is correct
19 Correct 1166 ms 144304 KB Output is correct
20 Execution timed out 4050 ms 204384 KB Time limit exceeded
21 Halted 0 ms 0 KB -