oj.uz

Submission #538912

# Submission time Handle Problem Language Result Execution time Memory
538912 2022-03-18T03:36:45 Z Monarchuwu Triple Jump (JOI19_jumps) C++17
19 / 100
 451 ms 127448 KB 
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 5000 + 3;
int n, lg[N];
ll a[13][N];

int get(int l, int r) {
    int k = lg[r - l + 1];
    return max(a[k][l], a[k][r - (1 << k) + 1]);
}

ll dp[N][N];
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[0][i];

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

    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;

    for (int i = 1; i <= n; ++i)
        for (int k = i + 2; k <= n; ++k)
            dp[i][k] = a[0][i] + get(i + 1, (i + k) >> 1) + a[0][k];

    for (int len = 3; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j)
            dp[i][j] = max({ dp[i][j - 1], dp[i + 1][j], a[0][i] + get(i + 1,(i + j) >> 1) + a[0][j] });

    int q, l, r; cin >> q; while (q--) {
        cin >> l >> r;
        cout << dp[l][r] << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 712 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 1 ms 736 KB Output is correct
10 Correct 1 ms 708 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 712 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 1 ms 736 KB Output is correct
10 Correct 1 ms 708 KB Output is correct
11 Correct 386 ms 127408 KB Output is correct
12 Correct 389 ms 127396 KB Output is correct
13 Correct 411 ms 127364 KB Output is correct
14 Correct 430 ms 127448 KB Output is correct
15 Correct 451 ms 127432 KB Output is correct
16 Correct 400 ms 126820 KB Output is correct
17 Correct 411 ms 126668 KB Output is correct
18 Correct 413 ms 126668 KB Output is correct
19 Correct 397 ms 127320 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 2300 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 1 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 712 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 1 ms 736 KB Output is correct
10 Correct 1 ms 708 KB Output is correct
11 Correct 386 ms 127408 KB Output is correct
12 Correct 389 ms 127396 KB Output is correct
13 Correct 411 ms 127364 KB Output is correct
14 Correct 430 ms 127448 KB Output is correct
15 Correct 451 ms 127432 KB Output is correct
16 Correct 400 ms 126820 KB Output is correct
17 Correct 411 ms 126668 KB Output is correct
18 Correct 413 ms 126668 KB Output is correct
19 Correct 397 ms 127320 KB Output is correct
20 Runtime error 10 ms 2300 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -