Submission #677807

#	Time	Username	Problem	Language	Result	Execution time	Memory
677807		puppy	Triple Jump (JOI19_jumps)	C++17	19 / 100	4053 ms	206952 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 dp2[5005][5005];
int dp3[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);
    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);
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i - 2; j >= 1; j--) {
            dp2[j][i] = max(dp2[j+1][i], dp[j][i]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 2; j <= n; j++) {
            dp3[i][j] = max(dp3[i][j-1], dp2[i][j]);
        }
    }
    int Q; cin >> Q;
    while (Q--) {
        int l, r; cin >> l >> r;
        cout << dp3[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: 14 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54