Submission #677805

#	Time	Username	Problem	Language	Result	Execution time	Memory
677805		puppy	Triple Jump (JOI19_jumps)	C++17	5 / 100	4103 ms	524288 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

struct maxseg
{
    vector<int> tree;
    maxseg(int siz){tree.resize(1<<((int)ceil(log2(siz))+1));}
    int init(int s, int e, int node, vector<int> &arr)
    {
        if(s==e) return tree[node] = arr[s];
        return tree[node] = max(init(s, (s+e)/2, 2*node, arr), init((s+e)/2+1, e, 2*node+1, arr));
    }
    void upd(int s, int e, int node, int idx, int val)
    {
        if(e<idx|idx<s) return;
        if(s==e){
            tree[node] = val; return;
        }
        upd(s, (s+e)/2, 2*node, idx, val); upd((s+e)/2+1, e, 2*node+1, idx, val);
        tree[node] = max(tree[2*node],  tree[2*node+1]);
    }
    int query(int s, int e, int node, int l, int r)
    {
        if(e<l||r<s) return 0;
        if(l<=s&&e<=r) return tree[node];
        return max(query(s, (s+e)/2, 2*node, l, r), query((s+e)/2+1, e, 2*node+1, l, r));
    }
};

int dp[5005][5005];
int a[5005];
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<int> tmp(n+1);
    for (int i = 1; i <= n; i++){cin >> a[i]; tmp[i] = a[i];}
    maxseg seg(n);
    seg.init(1, n, 1, tmp);
    vector<vector<int>> ini(n+1, vector<int>(n+1));
    for (int i = 1; i <= n; i++) {
        for (int j = i + 2; j <= n; j++) {
            //사잇값 범위 i + 1 ~ (i + j) / 2
            dp[i][j] = a[i] + a[j] + seg.query(1, n, 1, i + 1, (i + j) / 2);
            ini[j][i] = dp[i][j];
        }
    }
    vector<maxseg> seg2(n+1, n);
    for (int i = 1; i <= n; i++) {
        seg2[i].init(1, n, 1, ini[i]);
    }
    //max(dp[i][j+1], ..., dp[j][j+1]) = seg2[j+1].query(i, j - 1)
    for (int i = 1; i <= n - 2; i++) {
        dp[i][i+2] = a[i] + a[i+1] + a[i+2];
        for (int j = i + 3; j <= n; j++) {
            //dp[i][j] 갱신
            dp[i][j] = max(dp[i][j-1], seg2[j].query(1, n, 1, i, j - 2));
        }
    }
    int Q; cin >> Q;
    while (Q--) {
        int l, r; cin >> l >> r;
        cout << dp[l][r] << '\n';
    }
}

Compilation message (stderr)

jumps.cpp: In member function 'void maxseg::upd(int, int, int, int, int)':
jumps.cpp:15:13: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   15 |         if(e<idx|idx<s) return;
      |            ~^~~~

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