Submission #1253400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253400		ankite	3단 점프 (JOI19_jumps)	C++20	19 / 100	3119 ms	149500 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 z=3; z<=n; z++) {
        for (int x = z-2; x>=1; x--) {
            pre[x][z] = max(max(pre[x + 1][z], pre[x][z-1]), a[x] + get(x + 1, (x + z) >> 1) + a[z]);
        }
    }

//    for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) cout << pre[i][j] << ' '; print(); }
    for (int i=1; i<=q; i++) {
        int l = Q[i].first, r = Q[i].second;
        cout << pre[l][r] << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    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: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54