Submission #564182

#	Time	Username	Problem	Language	Result	Execution time	Memory
564182		4fecta	Triple Jump (JOI19_jumps)	C++17	46 / 100	4034 ms	127344 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

const int MN = 500005;

int n, q, a[MN], l, r, st[MN * 4], dp[5005][5005];

void build(int l, int r, int idx) {
    if (l == r) {st[idx] = a[l]; return;}
    int mid = (l + r) >> 1;
    build(l, mid, idx * 2), build(mid + 1, r, idx * 2 + 1);
    st[idx] = max(st[idx * 2], st[idx * 2 + 1]);
}

int qry(int l, int r, int x, int y, int idx) {
    if (r < x || l > y || r < l) return -0x3f3f3f3f;
    if (r <= y && l >= x) return st[idx];
    int mid = (l + r) >> 1;
    return max(qry(l, mid, x, y, idx * 2), qry(mid + 1, r, x, y, idx * 2 + 1));
}

int twos(int j, int i, int l, int r) {
    if (j > i) swap(i, j);
    int ret = 0;
    int lo = max(l, j - (i - j));
    ret = max(ret, qry(1, n, lo, j - 1, 1) + a[j] + a[i]);
    int hi = i + (i - j);
    ret = max(ret, qry(1, n, hi, r, 1) + a[j] + a[i]);
    int mid = (j + i) / 2;
    ret = max(ret, qry(1, n, j + 1, mid, 1) + a[j] + a[i]);
    return ret;
}

int check(int i, int l, int r) {
    int ret = 0;
    for (int j = l; j <= r; j++) {
        if (j != i) ret = max(ret, twos(i, j, l, r));
    }
    return ret;
}

int32_t main() {
    boost();

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, n, 1);
    if (n <= 5000) {
        for (int len = 3; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                if (len == 3) dp[l][r] = a[l] + a[l + 1] + a[r];
                else dp[l][r] = max({dp[l + 1][r], dp[l][r - 1], twos(l, r, l, r)});
            }
        }
    }
    cin >> q;
    while (q--) {
        cin >> l >> r;
        if (n <= 5000) printf("%lld\n", dp[l][r]);
        else {
            vector<pii> v;
            for (int i = l; i <= r; i++) v.push_back({a[i], i});
            sort(v.begin(), v.end(), greater<>());
            int ans = 0;
            for (int i = 0; i < min((int) v.size(), 20ll); i++) {
                ans = max(ans, check(v[i].s, l, r));
            }
            printf("%lld\n", ans);
        }
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54