oj.uz

Submission #538933

# Submission time Handle Problem Language Result Execution time Memory
538933 2022-03-18T04:54:25 Z Monarchuwu Triple Jump (JOI19_jumps) C++17
46 / 100
 489 ms 72608 KB 
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
typedef long long ll;

const int N = 5e5 + 5, N2 = 5000 + 3, inf = 1e9 + 7;
int n, lg[N];
int a[19][N];

void build() {
    for (int j = 0; j < 18; ++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;
}
int get(int l, int r) {
    if (r < 1 || n < l || r < l) return -inf;
    int k = lg[r - l + 1];
    return max(a[k][l], a[k][r - (1 << k) + 1]);
}

int dp[N2][N2];
void subtask12() {
    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';
    }
}

int calc(int p1, int p2) {
    return max({ get(max(1, p1 * 2 - p2), p1 - 1), get(p1 + 1, (p1 + p2) >> 1), get(p2 * 2 - p1, n) });
}
int idx[N];
void subtask3() {
    iota(idx + 1, idx + n + 1, 1);
    sort(idx + 1, idx + n + 1, [](int i, int j) { return a[0][i] > a[0][j]; });

    int ans(-inf);
    for (int p = 1; p <= 20; ++p) {
        int i = idx[p];

        for (int j = 1; j < i; ++j)
            ans = max(ans, a[0][j] + calc(j, i) + a[0][i]);
        for (int j = i + 1; j <= n; ++j)
            ans = max(ans, a[0][i] + calc(i, j) + a[0][j]);
    }
    cout << ans << '\n';
}

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

    if (n <= 5000)
        subtask12();
    else subtask3();
}
/**  /\_/\
 *  (= ._.)
 *  / >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 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 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 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 404 ms 72608 KB Output is correct
12 Correct 414 ms 72572 KB Output is correct
13 Correct 442 ms 72560 KB Output is correct
14 Correct 452 ms 72592 KB Output is correct
15 Correct 385 ms 72520 KB Output is correct
16 Correct 489 ms 72080 KB Output is correct
17 Correct 452 ms 71868 KB Output is correct
18 Correct 381 ms 71852 KB Output is correct
19 Correct 449 ms 72436 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 15060 KB Output is correct
2 Correct 96 ms 15056 KB Output is correct
3 Correct 88 ms 15060 KB Output is correct
4 Correct 92 ms 14984 KB Output is correct
5 Correct 96 ms 16696 KB Output is correct
6 Correct 88 ms 16152 KB Output is correct
7 Correct 90 ms 16044 KB Output is correct
8 Correct 85 ms 15948 KB Output is correct
9 Correct 96 ms 16372 KB Output is correct

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 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 404 ms 72608 KB Output is correct
12 Correct 414 ms 72572 KB Output is correct
13 Correct 442 ms 72560 KB Output is correct
14 Correct 452 ms 72592 KB Output is correct
15 Correct 385 ms 72520 KB Output is correct
16 Correct 489 ms 72080 KB Output is correct
17 Correct 452 ms 71868 KB Output is correct
18 Correct 381 ms 71852 KB Output is correct
19 Correct 449 ms 72436 KB Output is correct
20 Correct 94 ms 15060 KB Output is correct
21 Correct 96 ms 15056 KB Output is correct
22 Correct 88 ms 15060 KB Output is correct
23 Correct 92 ms 14984 KB Output is correct
24 Correct 96 ms 16696 KB Output is correct
25 Correct 88 ms 16152 KB Output is correct
26 Correct 90 ms 16044 KB Output is correct
27 Correct 85 ms 15948 KB Output is correct
28 Correct 96 ms 16372 KB Output is correct
29 Incorrect 263 ms 43904 KB Output isn't correct
30 Halted 0 ms 0 KB -