oj.uz

Submission #927764

# Submission time Handle Problem Language Result Execution time Memory
927764 2024-02-15T10:05:34 Z boris_mihov Two Dishes (JOI19_dishes) C++17
65 / 100
 10000 ms 302704 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 20;
const llong INF = 1e18;

int n, m;
template <typename T>
struct Fenwick
{
    T tree[MAXN];
    void update(int pos, T val)
    {
        for (int idx = pos ; idx <= m ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    T query(int pos)
    {
        T res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    int findKthZero(int k)
    {
        int idx = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (idx + (1 << log) <= m && (1 << log) - tree[idx + (1 << log)] < k)
            {
                idx += (1 << log);
                k -= (1 << log) - tree[idx];
            }
        }

        return idx + 1;
    }

    int findKthOne(int k)
    {
        int idx = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (idx + (1 << log) <= m && tree[idx + (1 << log)] < k)
            {
                idx += (1 << log);
                k -= tree[idx];
            }
        }

        return idx + 1;
    }
};

struct SegmentTree
{
    struct Node
    {
        llong value;
        llong lazy;

        Node()
        {
            value = lazy;
        }
    };

    Node tree[4*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].value += tree[node].lazy;
        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void rangeUpdate(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = queryVal;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        rangeUpdate(l, mid, 2*node, queryL, queryR, queryVal);
        rangeUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
    }

    void setUpdate(int l, int r, int node, int queryPos, llong queryVal)
    {
        push(node, l, r);
        if (queryPos < l || r < queryPos)
        {
            return;
        }

        if (l == r)
        {
            tree[node].value = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        setUpdate(l, mid, 2*node, queryPos, queryVal);
        setUpdate(mid + 1, r, 2*node + 1, queryPos, queryVal);
    }

    llong query(int l, int r, int node, int queryPos)
    {
        push(node, l, r);
        if (l == r)
        {
            return tree[node].value;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) return query(l, mid, 2*node, queryPos);
        else return query(mid + 1, r, 2*node + 1, queryPos);
    }

    void update(int pos, llong value)
    {
        setUpdate(1, m + 1, 1, pos, value);
    }

    void rangeUpdate(int l, int r, int value)
    {
        rangeUpdate(1, m + 1, 1, l, r, value);
    }

    llong query(int pos)
    {
        return query(1, m + 1, 1, pos);
    }
};

Fenwick <int> fenwickNext;
Fenwick <llong> fenwickActive;
SegmentTree dp;

struct Dish
{
    int time;
    llong limit;
    int reward;
    int idx;
    bool type;
};

Dish a[MAXN];
Dish b[MAXN];
llong prefixA[MAXN];
llong prefixB[MAXN];
bool isNext[MAXN];
bool isActive[MAXN];
llong dpBorderM[MAXN];
llong active[MAXN];

int globalRow;
llong findValue(int col)
{
    if (col == m + 1)
    {
        return dp.query(m + 1);
    }

    int cnt = col - 1 - fenwickNext.query(col - 1);
    int pos = m;
    
    if (cnt != m - fenwickNext.query(m))
    {
        pos = fenwickNext.findKthZero(cnt + 1);
    }

    return fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp.query(pos);
}

void fix(int col)
{
    assert(col <= m);
    llong curr = dp.query(col);
    llong next = findValue(col + 1) + active[col];
    int res = isNext[col];
    fenwickNext.update(col, -res);

    int nextVal = 0;
    isNext[col] = false;
    if (curr < next) 
    {
        nextVal = 1;
        isNext[col] = true;
        fenwickNext.update(col, 1);
    }

    dp.update(col, std::max(curr, next));
    if (col > 1)
    {
        int queryRes = fenwickNext.query(col - 1);
        if (queryRes < col - 1)
        {
            int cntZeroesToNow = col - 1 - queryRes;
            int pos = fenwickNext.findKthZero(cntZeroesToNow);
            llong nextVal = findValue(pos + 1) + active[pos];
            if (nextVal > findValue(pos)) fix(pos);
        }

        if (queryRes > 0)
        {
            int cntOnesToNow = queryRes;
            int pos = fenwickNext.findKthOne(cntOnesToNow);
            llong nextVal = findValue(pos + 1) + active[pos];
            if (nextVal > findValue(pos)) fix(pos);
        }
    }
}

void applyUpdate(int to, int val)
{
    dp.rangeUpdate(1, to, val);
}

std::vector <int> activateAt[MAXN];
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        prefixA[i] = prefixA[i - 1] + a[i].time;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        prefixB[i] = prefixB[i - 1] + b[i].time;
    }

    for (int aPos = n ; aPos >= 1 ; --aPos)
    {
        dpBorderM[aPos] = dpBorderM[aPos + 1] + (prefixA[aPos - 1] + prefixB[m] + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int l = 0, r = n + 2, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (prefixA[mid - 1] + prefixB[i] <= b[i].limit) l = mid;
            else r = mid;
        }

        activateAt[l].push_back(i);
    }

    globalRow = n + 1;
    for (int i = 1 ; i <= m ; ++i)
    {
        fenwickNext.update(i, 1);
        isNext[i] = true;
    }

    std::sort(activateAt[n + 1].begin(), activateAt[n + 1].end(), std::greater <int> ());
    for (const int &idx : activateAt[globalRow])
    {
        active[idx] = b[idx].reward;
        fenwickActive.update(idx, b[idx].reward);
        fix(idx);
    }

    for (globalRow = n ; globalRow >= 1 ; --globalRow)
    {
        for (const int &idx : activateAt[globalRow])
        {
            dp.update(idx, findValue(idx));
        }
    
        int l = 0, r = m + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (prefixA[globalRow] + prefixB[mid - 1] <= a[globalRow].limit) l = mid;
            else r = mid;
        }

        if (l > 0)
        {
            dp.update(l, findValue(l));
        }

        for (const int &idx : activateAt[globalRow])
        {
            active[idx] = b[idx].reward;
            fenwickActive.update(idx, b[idx].reward);
        }

        if (l > 0) activateAt[globalRow].push_back(l);
        applyUpdate(l, a[globalRow].reward);

        dp.update(m + 1, dpBorderM[globalRow]);
        activateAt[globalRow].push_back(m);
        std::sort(activateAt[globalRow].begin(), activateAt[globalRow].end(), std::greater <int> ());

        for (const int &idx : activateAt[globalRow])
        {
            fix(idx);
        }
    }

    globalRow++;
    std::cout << findValue(1) << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i].time >> a[i].limit >> a[i].reward;
        a[i].idx = i;
        a[i].type = false;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> b[i].time >> b[i].limit >> b[i].reward;
        b[i].idx = i;
        a[i].type = true;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

signed main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

dishes.cpp: In function 'void fix(int)':
dishes.cpp:218:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
  218 |     int nextVal = 0;
      |         ^~~~~~~
dishes.cpp: In constructor 'SegmentTree::Node::Node()':
dishes.cpp:79:21: warning: '*<unknown>.SegmentTree::Node::lazy' is used uninitialized in this function [-Wuninitialized]
   79 |             value = lazy;
      |                     ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 120820 KB Output is correct
2 Correct 722 ms 122388 KB Output is correct
3 Correct 557 ms 124608 KB Output is correct
4 Correct 569 ms 119976 KB Output is correct
5 Correct 39 ms 94036 KB Output is correct
6 Correct 756 ms 122056 KB Output is correct
7 Correct 173 ms 114384 KB Output is correct
8 Correct 127 ms 110408 KB Output is correct
9 Correct 518 ms 124744 KB Output is correct
10 Correct 893 ms 120896 KB Output is correct
11 Correct 506 ms 124604 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94036 KB Output is correct
2 Correct 38 ms 93960 KB Output is correct
3 Correct 39 ms 94004 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 38 ms 94036 KB Output is correct
7 Correct 38 ms 94020 KB Output is correct
8 Correct 38 ms 94036 KB Output is correct
9 Correct 39 ms 94032 KB Output is correct
10 Correct 39 ms 94036 KB Output is correct
11 Correct 47 ms 93880 KB Output is correct
12 Correct 38 ms 94032 KB Output is correct
13 Correct 38 ms 93824 KB Output is correct
14 Correct 38 ms 94032 KB Output is correct
15 Correct 38 ms 94020 KB Output is correct
16 Correct 44 ms 93860 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94036 KB Output is correct
2 Correct 38 ms 93960 KB Output is correct
3 Correct 39 ms 94004 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 38 ms 94036 KB Output is correct
7 Correct 38 ms 94020 KB Output is correct
8 Correct 38 ms 94036 KB Output is correct
9 Correct 39 ms 94032 KB Output is correct
10 Correct 39 ms 94036 KB Output is correct
11 Correct 47 ms 93880 KB Output is correct
12 Correct 38 ms 94032 KB Output is correct
13 Correct 38 ms 93824 KB Output is correct
14 Correct 38 ms 94032 KB Output is correct
15 Correct 38 ms 94020 KB Output is correct
16 Correct 44 ms 93860 KB Output is correct
17 Correct 43 ms 94044 KB Output is correct
18 Correct 42 ms 94032 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 44 ms 93948 KB Output is correct
21 Correct 46 ms 94208 KB Output is correct
22 Correct 49 ms 94636 KB Output is correct
23 Correct 48 ms 93952 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94036 KB Output is correct
2 Correct 38 ms 93960 KB Output is correct
3 Correct 39 ms 94004 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 38 ms 94036 KB Output is correct
7 Correct 38 ms 94020 KB Output is correct
8 Correct 38 ms 94036 KB Output is correct
9 Correct 39 ms 94032 KB Output is correct
10 Correct 39 ms 94036 KB Output is correct
11 Correct 47 ms 93880 KB Output is correct
12 Correct 38 ms 94032 KB Output is correct
13 Correct 38 ms 93824 KB Output is correct
14 Correct 38 ms 94032 KB Output is correct
15 Correct 38 ms 94020 KB Output is correct
16 Correct 44 ms 93860 KB Output is correct
17 Correct 43 ms 94044 KB Output is correct
18 Correct 42 ms 94032 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 44 ms 93948 KB Output is correct
21 Correct 46 ms 94208 KB Output is correct
22 Correct 49 ms 94636 KB Output is correct
23 Correct 48 ms 93952 KB Output is correct
24 Correct 420 ms 124612 KB Output is correct
25 Correct 475 ms 121564 KB Output is correct
26 Correct 570 ms 124796 KB Output is correct
27 Correct 495 ms 122704 KB Output is correct
28 Correct 814 ms 124936 KB Output is correct
29 Correct 487 ms 124776 KB Output is correct
30 Correct 1618 ms 124504 KB Output is correct
31 Correct 206 ms 114524 KB Output is correct
32 Correct 115 ms 110492 KB Output is correct
33 Correct 973 ms 124160 KB Output is correct
34 Correct 1169 ms 124572 KB Output is correct
35 Correct 1637 ms 124092 KB Output is correct
36 Correct 1586 ms 124224 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94036 KB Output is correct
2 Correct 38 ms 93960 KB Output is correct
3 Correct 39 ms 94004 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 38 ms 94036 KB Output is correct
7 Correct 38 ms 94020 KB Output is correct
8 Correct 38 ms 94036 KB Output is correct
9 Correct 39 ms 94032 KB Output is correct
10 Correct 39 ms 94036 KB Output is correct
11 Correct 47 ms 93880 KB Output is correct
12 Correct 38 ms 94032 KB Output is correct
13 Correct 38 ms 93824 KB Output is correct
14 Correct 38 ms 94032 KB Output is correct
15 Correct 38 ms 94020 KB Output is correct
16 Correct 44 ms 93860 KB Output is correct
17 Correct 43 ms 94044 KB Output is correct
18 Correct 42 ms 94032 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 44 ms 93948 KB Output is correct
21 Correct 46 ms 94208 KB Output is correct
22 Correct 49 ms 94636 KB Output is correct
23 Correct 48 ms 93952 KB Output is correct
24 Correct 420 ms 124612 KB Output is correct
25 Correct 475 ms 121564 KB Output is correct
26 Correct 570 ms 124796 KB Output is correct
27 Correct 495 ms 122704 KB Output is correct
28 Correct 814 ms 124936 KB Output is correct
29 Correct 487 ms 124776 KB Output is correct
30 Correct 1618 ms 124504 KB Output is correct
31 Correct 206 ms 114524 KB Output is correct
32 Correct 115 ms 110492 KB Output is correct
33 Correct 973 ms 124160 KB Output is correct
34 Correct 1169 ms 124572 KB Output is correct
35 Correct 1637 ms 124092 KB Output is correct
36 Correct 1586 ms 124224 KB Output is correct
37 Correct 581 ms 124784 KB Output is correct
38 Correct 507 ms 120912 KB Output is correct
39 Correct 856 ms 120912 KB Output is correct
40 Correct 765 ms 136500 KB Output is correct
41 Correct 39 ms 94032 KB Output is correct
42 Correct 1690 ms 124288 KB Output is correct
43 Correct 1016 ms 124032 KB Output is correct
44 Correct 1127 ms 124384 KB Output is correct
45 Correct 1566 ms 124184 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94036 KB Output is correct
2 Correct 38 ms 93960 KB Output is correct
3 Correct 39 ms 94004 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 38 ms 94036 KB Output is correct
7 Correct 38 ms 94020 KB Output is correct
8 Correct 38 ms 94036 KB Output is correct
9 Correct 39 ms 94032 KB Output is correct
10 Correct 39 ms 94036 KB Output is correct
11 Correct 47 ms 93880 KB Output is correct
12 Correct 38 ms 94032 KB Output is correct
13 Correct 38 ms 93824 KB Output is correct
14 Correct 38 ms 94032 KB Output is correct
15 Correct 38 ms 94020 KB Output is correct
16 Correct 44 ms 93860 KB Output is correct
17 Correct 43 ms 94044 KB Output is correct
18 Correct 42 ms 94032 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 44 ms 93948 KB Output is correct
21 Correct 46 ms 94208 KB Output is correct
22 Correct 49 ms 94636 KB Output is correct
23 Correct 48 ms 93952 KB Output is correct
24 Correct 420 ms 124612 KB Output is correct
25 Correct 475 ms 121564 KB Output is correct
26 Correct 570 ms 124796 KB Output is correct
27 Correct 495 ms 122704 KB Output is correct
28 Correct 814 ms 124936 KB Output is correct
29 Correct 487 ms 124776 KB Output is correct
30 Correct 1618 ms 124504 KB Output is correct
31 Correct 206 ms 114524 KB Output is correct
32 Correct 115 ms 110492 KB Output is correct
33 Correct 973 ms 124160 KB Output is correct
34 Correct 1169 ms 124572 KB Output is correct
35 Correct 1637 ms 124092 KB Output is correct
36 Correct 1586 ms 124224 KB Output is correct
37 Correct 581 ms 124784 KB Output is correct
38 Correct 507 ms 120912 KB Output is correct
39 Correct 856 ms 120912 KB Output is correct
40 Correct 765 ms 136500 KB Output is correct
41 Correct 39 ms 94032 KB Output is correct
42 Correct 1690 ms 124288 KB Output is correct
43 Correct 1016 ms 124032 KB Output is correct
44 Correct 1127 ms 124384 KB Output is correct
45 Correct 1566 ms 124184 KB Output is correct
46 Correct 2940 ms 228584 KB Output is correct
47 Correct 2565 ms 224320 KB Output is correct
48 Correct 4758 ms 224584 KB Output is correct
49 Correct 3967 ms 302704 KB Output is correct
50 Execution timed out 10064 ms 224936 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 120820 KB Output is correct
2 Correct 722 ms 122388 KB Output is correct
3 Correct 557 ms 124608 KB Output is correct
4 Correct 569 ms 119976 KB Output is correct
5 Correct 39 ms 94036 KB Output is correct
6 Correct 756 ms 122056 KB Output is correct
7 Correct 173 ms 114384 KB Output is correct
8 Correct 127 ms 110408 KB Output is correct
9 Correct 518 ms 124744 KB Output is correct
10 Correct 893 ms 120896 KB Output is correct
11 Correct 506 ms 124604 KB Output is correct
12 Correct 38 ms 94036 KB Output is correct
13 Correct 38 ms 93960 KB Output is correct
14 Correct 39 ms 94004 KB Output is correct
15 Correct 38 ms 94044 KB Output is correct
16 Correct 38 ms 94040 KB Output is correct
17 Correct 38 ms 94036 KB Output is correct
18 Correct 38 ms 94020 KB Output is correct
19 Correct 38 ms 94036 KB Output is correct
20 Correct 39 ms 94032 KB Output is correct
21 Correct 39 ms 94036 KB Output is correct
22 Correct 47 ms 93880 KB Output is correct
23 Correct 38 ms 94032 KB Output is correct
24 Correct 38 ms 93824 KB Output is correct
25 Correct 38 ms 94032 KB Output is correct
26 Correct 38 ms 94020 KB Output is correct
27 Correct 44 ms 93860 KB Output is correct
28 Correct 43 ms 94044 KB Output is correct
29 Correct 42 ms 94032 KB Output is correct
30 Correct 48 ms 94032 KB Output is correct
31 Correct 44 ms 93948 KB Output is correct
32 Correct 46 ms 94208 KB Output is correct
33 Correct 49 ms 94636 KB Output is correct
34 Correct 48 ms 93952 KB Output is correct
35 Correct 420 ms 124612 KB Output is correct
36 Correct 475 ms 121564 KB Output is correct
37 Correct 570 ms 124796 KB Output is correct
38 Correct 495 ms 122704 KB Output is correct
39 Correct 814 ms 124936 KB Output is correct
40 Correct 487 ms 124776 KB Output is correct
41 Correct 1618 ms 124504 KB Output is correct
42 Correct 206 ms 114524 KB Output is correct
43 Correct 115 ms 110492 KB Output is correct
44 Correct 973 ms 124160 KB Output is correct
45 Correct 1169 ms 124572 KB Output is correct
46 Correct 1637 ms 124092 KB Output is correct
47 Correct 1586 ms 124224 KB Output is correct
48 Correct 581 ms 124784 KB Output is correct
49 Correct 507 ms 120912 KB Output is correct
50 Correct 856 ms 120912 KB Output is correct
51 Correct 765 ms 136500 KB Output is correct
52 Correct 39 ms 94032 KB Output is correct
53 Correct 1690 ms 124288 KB Output is correct
54 Correct 1016 ms 124032 KB Output is correct
55 Correct 1127 ms 124384 KB Output is correct
56 Correct 1566 ms 124184 KB Output is correct
57 Incorrect 676 ms 124612 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 120820 KB Output is correct
2 Correct 722 ms 122388 KB Output is correct
3 Correct 557 ms 124608 KB Output is correct
4 Correct 569 ms 119976 KB Output is correct
5 Correct 39 ms 94036 KB Output is correct
6 Correct 756 ms 122056 KB Output is correct
7 Correct 173 ms 114384 KB Output is correct
8 Correct 127 ms 110408 KB Output is correct
9 Correct 518 ms 124744 KB Output is correct
10 Correct 893 ms 120896 KB Output is correct
11 Correct 506 ms 124604 KB Output is correct
12 Correct 38 ms 94036 KB Output is correct
13 Correct 38 ms 93960 KB Output is correct
14 Correct 39 ms 94004 KB Output is correct
15 Correct 38 ms 94044 KB Output is correct
16 Correct 38 ms 94040 KB Output is correct
17 Correct 38 ms 94036 KB Output is correct
18 Correct 38 ms 94020 KB Output is correct
19 Correct 38 ms 94036 KB Output is correct
20 Correct 39 ms 94032 KB Output is correct
21 Correct 39 ms 94036 KB Output is correct
22 Correct 47 ms 93880 KB Output is correct
23 Correct 38 ms 94032 KB Output is correct
24 Correct 38 ms 93824 KB Output is correct
25 Correct 38 ms 94032 KB Output is correct
26 Correct 38 ms 94020 KB Output is correct
27 Correct 44 ms 93860 KB Output is correct
28 Correct 43 ms 94044 KB Output is correct
29 Correct 42 ms 94032 KB Output is correct
30 Correct 48 ms 94032 KB Output is correct
31 Correct 44 ms 93948 KB Output is correct
32 Correct 46 ms 94208 KB Output is correct
33 Correct 49 ms 94636 KB Output is correct
34 Correct 48 ms 93952 KB Output is correct
35 Correct 420 ms 124612 KB Output is correct
36 Correct 475 ms 121564 KB Output is correct
37 Correct 570 ms 124796 KB Output is correct
38 Correct 495 ms 122704 KB Output is correct
39 Correct 814 ms 124936 KB Output is correct
40 Correct 487 ms 124776 KB Output is correct
41 Correct 1618 ms 124504 KB Output is correct
42 Correct 206 ms 114524 KB Output is correct
43 Correct 115 ms 110492 KB Output is correct
44 Correct 973 ms 124160 KB Output is correct
45 Correct 1169 ms 124572 KB Output is correct
46 Correct 1637 ms 124092 KB Output is correct
47 Correct 1586 ms 124224 KB Output is correct
48 Correct 581 ms 124784 KB Output is correct
49 Correct 507 ms 120912 KB Output is correct
50 Correct 856 ms 120912 KB Output is correct
51 Correct 765 ms 136500 KB Output is correct
52 Correct 39 ms 94032 KB Output is correct
53 Correct 1690 ms 124288 KB Output is correct
54 Correct 1016 ms 124032 KB Output is correct
55 Correct 1127 ms 124384 KB Output is correct
56 Correct 1566 ms 124184 KB Output is correct
57 Correct 2940 ms 228584 KB Output is correct
58 Correct 2565 ms 224320 KB Output is correct
59 Correct 4758 ms 224584 KB Output is correct
60 Correct 3967 ms 302704 KB Output is correct
61 Execution timed out 10064 ms 224936 KB Time limit exceeded
62 Halted 0 ms 0 KB -