Submission #1253373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253373		ankite	Triple Jump (JOI19_jumps)	C++20	5 / 100	4094 ms	125344 KiB

jumps

#include <bits/stdc++.h>;
#define int long long
using namespace std;
using pii = pair<int, int>;

const int li = 5e5 + 10;
void print() { cerr << '\n'; }
template<typename T, typename... Args>
void print(T first, Args... rest) {
    cerr << first << ' ';
    print(rest...);
}

int n, a[li], q;
pii Q[li];

void solve1() {
    for (int i=1; i<=q; i++) {
        int l = Q[i].first, r = Q[i].second;
        int ans = 0;

        for (int z=l+2; z<=r; z++) {
            for (int x=l; x<=z-2; x++) {
                for (int y=x+1; y - x <= z - y; y++) {
                    ans = max(ans, a[x] + a[y] + a[z]);
                }
            }
        }

        cout << ans << '\n';
    }
}

int seg[li * 4];
int left(int id) { return (id << 1); }
int right(int id) { return (id << 1 | 1); }
void build(int id = 1, int l = 1, int r = n) {
    if (l == r) { seg[id] = a[l]; return; }

    int mid = (l + r) >> 1;
    build(left(id), l, mid);
    build(right(id), mid + 1, r);

    seg[id] = max(seg[left(id)], seg[right(id)]);
}
int get(int lo, int hi, int id = 1, int l = 1, int r = n) {
    if (r < lo  ||  l > hi) return 0;
    if (l >= lo  &&  r <= hi) return seg[id];

    int mid = (l + r) >> 1;
    return max(get(lo, hi, left(id), l, mid), get(lo, hi, right(id), mid + 1, r));
}

int pre[5001][5001];
void solve2() {
    build();
    for (int x=1; x<=n-2; x++) {
        for (int z = x + 2; z<=n; z++) {
            pre[x][z] = get(x + 1, ((z + x) >> 1)) + a[x] + a[z];
        }
    }

    for (int i=1; i<=q; i++) {
        int l = Q[i].first, r = Q[i].second;
        int ans = 0;
        for (int z=l+2; z<=r; z++) {
            for (int x=l; x<=z-2; x++) {
                ans = max(ans, pre[x][z]);
            }
        }

        cout << ans << '\n';
    }
}

signed main(){
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    cin >> q;
    for (int i=1; i<=q; i++) cin >> Q[i].first >> Q[i].second;
    solve2();

    return 0;
}

Compilation message (stderr)

jumps.cpp:1:25: warning: extra tokens at end of #include directive
    1 | #include <bits/stdc++.h>;
      |                         ^

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