oj.uz

Submission #538928

# Submission time Handle Problem Language Result Execution time Memory
538928 2022-03-18T04:40:49 Z Monarchuwu Triple Jump (JOI19_jumps) C++17
19 / 100
 439 ms 72696 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 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] + max({ get(1, j * 2 - i), get(j + 1, (j + i) >> 1), get(i * 2 - j, n) }) + a[0][i]);
        for (int j = i + 1; j <= n; ++j)
            ans = max(ans, a[0][i] + max({ get(1, i * 2 - j), get(i + 1, (i + j) >> 1), get(j * 2 - i, n) }) + 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 0 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 0 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 439 ms 72624 KB Output is correct
12 Correct 420 ms 72540 KB Output is correct
13 Correct 431 ms 72696 KB Output is correct
14 Correct 408 ms 72632 KB Output is correct
15 Correct 411 ms 72624 KB Output is correct
16 Correct 409 ms 71868 KB Output is correct
17 Correct 431 ms 71840 KB Output is correct
18 Correct 421 ms 71932 KB Output is correct
19 Correct 431 ms 72584 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 15064 KB Output is correct
2 Correct 72 ms 14980 KB Output is correct
3 Correct 66 ms 15180 KB Output is correct
4 Incorrect 78 ms 15040 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 439 ms 72624 KB Output is correct
12 Correct 420 ms 72540 KB Output is correct
13 Correct 431 ms 72696 KB Output is correct
14 Correct 408 ms 72632 KB Output is correct
15 Correct 411 ms 72624 KB Output is correct
16 Correct 409 ms 71868 KB Output is correct
17 Correct 431 ms 71840 KB Output is correct
18 Correct 421 ms 71932 KB Output is correct
19 Correct 431 ms 72584 KB Output is correct
20 Correct 80 ms 15064 KB Output is correct
21 Correct 72 ms 14980 KB Output is correct
22 Correct 66 ms 15180 KB Output is correct
23 Incorrect 78 ms 15040 KB Output isn't correct
24 Halted 0 ms 0 KB -