oj.uz

Submission #677807

# Submission time Handle Problem Language Result Execution time Memory
677807 2023-01-04T11:55:34 Z puppy Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 206952 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 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

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 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 2 ms 1568 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 2 ms 1568 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1534 ms 206696 KB Output is correct
12 Correct 1530 ms 206952 KB Output is correct
13 Correct 1572 ms 206596 KB Output is correct
14 Correct 1545 ms 206828 KB Output is correct
15 Correct 1546 ms 206852 KB Output is correct
16 Correct 1548 ms 206136 KB Output is correct
17 Correct 1558 ms 206220 KB Output is correct
18 Correct 1548 ms 205864 KB Output is correct
19 Correct 1542 ms 206632 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4053 ms 9508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 2 ms 1568 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 1534 ms 206696 KB Output is correct
12 Correct 1530 ms 206952 KB Output is correct
13 Correct 1572 ms 206596 KB Output is correct
14 Correct 1545 ms 206828 KB Output is correct
15 Correct 1546 ms 206852 KB Output is correct
16 Correct 1548 ms 206136 KB Output is correct
17 Correct 1558 ms 206220 KB Output is correct
18 Correct 1548 ms 205864 KB Output is correct
19 Correct 1542 ms 206632 KB Output is correct
20 Execution timed out 4053 ms 9508 KB Time limit exceeded
21 Halted 0 ms 0 KB -