oj.uz

Submission #677805

# Submission time Handle Problem Language Result Execution time Memory
677805 2023-01-04T11:50:37 Z puppy Triple Jump (JOI19_jumps) C++17
5 / 100
 4000 ms 524288 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 840 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 840 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 2 ms 840 KB Output is correct
10 Correct 2 ms 852 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 840 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 840 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 2 ms 840 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Execution timed out 4103 ms 486500 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 244 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 840 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 1 ms 840 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 840 KB Output is correct
9 Correct 2 ms 840 KB Output is correct
10 Correct 2 ms 852 KB Output is correct
11 Execution timed out 4103 ms 486500 KB Time limit exceeded
12 Halted 0 ms 0 KB -