Submission #927776

# Submission time Handle Problem Language Result Execution time Memory
927776 2024-02-15T10:27:24 Z boris_mihov Two Dishes (JOI19_dishes) C++17
65 / 100
10000 ms 302540 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 build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].value = (l == m + 1 ? 0LL : -INF);
            return;
        }

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

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

        if (tree[node].value != -INF) 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 build()
    {
        build(1, m + 1, 1);
    }

    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> ());
    dp.build();
    for (int i = 1 ; i <= m ; ++i)
    {
        dp.update(i, 0);
    }

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

    // for (int i = 1 ; i <= m + 1 ; ++i)
    // {
    //     std::cout << findValue(i) << ' ';
    // }

    // std::cout << '\n';

    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);
        }

        // for (int i = 1 ; i <= m ; ++i) fix(i);
        // for (int i = 1 ; i <= m + 1 ; ++i)
        // {
        //     std::cout << findValue(i) << ' ';
        // }

        // std::cout << '\n';
    }

    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:236:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
  236 |     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;
      |                     ^~~~
# Verdict Execution time Memory Grader output
1 Correct 744 ms 120832 KB Output is correct
2 Correct 746 ms 121984 KB Output is correct
3 Correct 515 ms 124672 KB Output is correct
4 Correct 586 ms 120020 KB Output is correct
5 Correct 38 ms 93972 KB Output is correct
6 Correct 785 ms 122024 KB Output is correct
7 Correct 195 ms 114380 KB Output is correct
8 Correct 124 ms 110416 KB Output is correct
9 Correct 520 ms 124624 KB Output is correct
10 Correct 906 ms 120888 KB Output is correct
11 Correct 499 ms 124820 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 93840 KB Output is correct
2 Correct 39 ms 94036 KB Output is correct
3 Correct 38 ms 94036 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 44 ms 94288 KB Output is correct
7 Correct 45 ms 94036 KB Output is correct
8 Correct 38 ms 94032 KB Output is correct
9 Correct 38 ms 94032 KB Output is correct
10 Correct 38 ms 94036 KB Output is correct
11 Correct 38 ms 93816 KB Output is correct
12 Correct 38 ms 94044 KB Output is correct
13 Correct 38 ms 94000 KB Output is correct
14 Correct 39 ms 93916 KB Output is correct
15 Correct 43 ms 94028 KB Output is correct
16 Correct 42 ms 94044 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 93840 KB Output is correct
2 Correct 39 ms 94036 KB Output is correct
3 Correct 38 ms 94036 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 44 ms 94288 KB Output is correct
7 Correct 45 ms 94036 KB Output is correct
8 Correct 38 ms 94032 KB Output is correct
9 Correct 38 ms 94032 KB Output is correct
10 Correct 38 ms 94036 KB Output is correct
11 Correct 38 ms 93816 KB Output is correct
12 Correct 38 ms 94044 KB Output is correct
13 Correct 38 ms 94000 KB Output is correct
14 Correct 39 ms 93916 KB Output is correct
15 Correct 43 ms 94028 KB Output is correct
16 Correct 42 ms 94044 KB Output is correct
17 Correct 41 ms 94024 KB Output is correct
18 Correct 42 ms 94036 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 46 ms 94020 KB Output is correct
21 Correct 47 ms 94032 KB Output is correct
22 Correct 52 ms 94036 KB Output is correct
23 Correct 48 ms 94160 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 93840 KB Output is correct
2 Correct 39 ms 94036 KB Output is correct
3 Correct 38 ms 94036 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 44 ms 94288 KB Output is correct
7 Correct 45 ms 94036 KB Output is correct
8 Correct 38 ms 94032 KB Output is correct
9 Correct 38 ms 94032 KB Output is correct
10 Correct 38 ms 94036 KB Output is correct
11 Correct 38 ms 93816 KB Output is correct
12 Correct 38 ms 94044 KB Output is correct
13 Correct 38 ms 94000 KB Output is correct
14 Correct 39 ms 93916 KB Output is correct
15 Correct 43 ms 94028 KB Output is correct
16 Correct 42 ms 94044 KB Output is correct
17 Correct 41 ms 94024 KB Output is correct
18 Correct 42 ms 94036 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 46 ms 94020 KB Output is correct
21 Correct 47 ms 94032 KB Output is correct
22 Correct 52 ms 94036 KB Output is correct
23 Correct 48 ms 94160 KB Output is correct
24 Correct 456 ms 124872 KB Output is correct
25 Correct 488 ms 121508 KB Output is correct
26 Correct 621 ms 124552 KB Output is correct
27 Correct 517 ms 122876 KB Output is correct
28 Correct 873 ms 124852 KB Output is correct
29 Correct 516 ms 124600 KB Output is correct
30 Correct 1691 ms 124152 KB Output is correct
31 Correct 230 ms 114448 KB Output is correct
32 Correct 121 ms 110408 KB Output is correct
33 Correct 1048 ms 124404 KB Output is correct
34 Correct 1206 ms 124516 KB Output is correct
35 Correct 1682 ms 124184 KB Output is correct
36 Correct 1580 ms 124496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 93840 KB Output is correct
2 Correct 39 ms 94036 KB Output is correct
3 Correct 38 ms 94036 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 44 ms 94288 KB Output is correct
7 Correct 45 ms 94036 KB Output is correct
8 Correct 38 ms 94032 KB Output is correct
9 Correct 38 ms 94032 KB Output is correct
10 Correct 38 ms 94036 KB Output is correct
11 Correct 38 ms 93816 KB Output is correct
12 Correct 38 ms 94044 KB Output is correct
13 Correct 38 ms 94000 KB Output is correct
14 Correct 39 ms 93916 KB Output is correct
15 Correct 43 ms 94028 KB Output is correct
16 Correct 42 ms 94044 KB Output is correct
17 Correct 41 ms 94024 KB Output is correct
18 Correct 42 ms 94036 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 46 ms 94020 KB Output is correct
21 Correct 47 ms 94032 KB Output is correct
22 Correct 52 ms 94036 KB Output is correct
23 Correct 48 ms 94160 KB Output is correct
24 Correct 456 ms 124872 KB Output is correct
25 Correct 488 ms 121508 KB Output is correct
26 Correct 621 ms 124552 KB Output is correct
27 Correct 517 ms 122876 KB Output is correct
28 Correct 873 ms 124852 KB Output is correct
29 Correct 516 ms 124600 KB Output is correct
30 Correct 1691 ms 124152 KB Output is correct
31 Correct 230 ms 114448 KB Output is correct
32 Correct 121 ms 110408 KB Output is correct
33 Correct 1048 ms 124404 KB Output is correct
34 Correct 1206 ms 124516 KB Output is correct
35 Correct 1682 ms 124184 KB Output is correct
36 Correct 1580 ms 124496 KB Output is correct
37 Correct 591 ms 124756 KB Output is correct
38 Correct 525 ms 120792 KB Output is correct
39 Correct 881 ms 120696 KB Output is correct
40 Correct 801 ms 136424 KB Output is correct
41 Correct 39 ms 93940 KB Output is correct
42 Correct 1626 ms 124080 KB Output is correct
43 Correct 984 ms 124256 KB Output is correct
44 Correct 1181 ms 124436 KB Output is correct
45 Correct 1642 ms 124180 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 93840 KB Output is correct
2 Correct 39 ms 94036 KB Output is correct
3 Correct 38 ms 94036 KB Output is correct
4 Correct 38 ms 94044 KB Output is correct
5 Correct 38 ms 94040 KB Output is correct
6 Correct 44 ms 94288 KB Output is correct
7 Correct 45 ms 94036 KB Output is correct
8 Correct 38 ms 94032 KB Output is correct
9 Correct 38 ms 94032 KB Output is correct
10 Correct 38 ms 94036 KB Output is correct
11 Correct 38 ms 93816 KB Output is correct
12 Correct 38 ms 94044 KB Output is correct
13 Correct 38 ms 94000 KB Output is correct
14 Correct 39 ms 93916 KB Output is correct
15 Correct 43 ms 94028 KB Output is correct
16 Correct 42 ms 94044 KB Output is correct
17 Correct 41 ms 94024 KB Output is correct
18 Correct 42 ms 94036 KB Output is correct
19 Correct 48 ms 94032 KB Output is correct
20 Correct 46 ms 94020 KB Output is correct
21 Correct 47 ms 94032 KB Output is correct
22 Correct 52 ms 94036 KB Output is correct
23 Correct 48 ms 94160 KB Output is correct
24 Correct 456 ms 124872 KB Output is correct
25 Correct 488 ms 121508 KB Output is correct
26 Correct 621 ms 124552 KB Output is correct
27 Correct 517 ms 122876 KB Output is correct
28 Correct 873 ms 124852 KB Output is correct
29 Correct 516 ms 124600 KB Output is correct
30 Correct 1691 ms 124152 KB Output is correct
31 Correct 230 ms 114448 KB Output is correct
32 Correct 121 ms 110408 KB Output is correct
33 Correct 1048 ms 124404 KB Output is correct
34 Correct 1206 ms 124516 KB Output is correct
35 Correct 1682 ms 124184 KB Output is correct
36 Correct 1580 ms 124496 KB Output is correct
37 Correct 591 ms 124756 KB Output is correct
38 Correct 525 ms 120792 KB Output is correct
39 Correct 881 ms 120696 KB Output is correct
40 Correct 801 ms 136424 KB Output is correct
41 Correct 39 ms 93940 KB Output is correct
42 Correct 1626 ms 124080 KB Output is correct
43 Correct 984 ms 124256 KB Output is correct
44 Correct 1181 ms 124436 KB Output is correct
45 Correct 1642 ms 124180 KB Output is correct
46 Correct 2993 ms 228516 KB Output is correct
47 Correct 2674 ms 224368 KB Output is correct
48 Correct 4579 ms 224516 KB Output is correct
49 Correct 4137 ms 302540 KB Output is correct
50 Execution timed out 10043 ms 223312 KB Time limit exceeded
51 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 744 ms 120832 KB Output is correct
2 Correct 746 ms 121984 KB Output is correct
3 Correct 515 ms 124672 KB Output is correct
4 Correct 586 ms 120020 KB Output is correct
5 Correct 38 ms 93972 KB Output is correct
6 Correct 785 ms 122024 KB Output is correct
7 Correct 195 ms 114380 KB Output is correct
8 Correct 124 ms 110416 KB Output is correct
9 Correct 520 ms 124624 KB Output is correct
10 Correct 906 ms 120888 KB Output is correct
11 Correct 499 ms 124820 KB Output is correct
12 Correct 38 ms 93840 KB Output is correct
13 Correct 39 ms 94036 KB Output is correct
14 Correct 38 ms 94036 KB Output is correct
15 Correct 38 ms 94044 KB Output is correct
16 Correct 38 ms 94040 KB Output is correct
17 Correct 44 ms 94288 KB Output is correct
18 Correct 45 ms 94036 KB Output is correct
19 Correct 38 ms 94032 KB Output is correct
20 Correct 38 ms 94032 KB Output is correct
21 Correct 38 ms 94036 KB Output is correct
22 Correct 38 ms 93816 KB Output is correct
23 Correct 38 ms 94044 KB Output is correct
24 Correct 38 ms 94000 KB Output is correct
25 Correct 39 ms 93916 KB Output is correct
26 Correct 43 ms 94028 KB Output is correct
27 Correct 42 ms 94044 KB Output is correct
28 Correct 41 ms 94024 KB Output is correct
29 Correct 42 ms 94036 KB Output is correct
30 Correct 48 ms 94032 KB Output is correct
31 Correct 46 ms 94020 KB Output is correct
32 Correct 47 ms 94032 KB Output is correct
33 Correct 52 ms 94036 KB Output is correct
34 Correct 48 ms 94160 KB Output is correct
35 Correct 456 ms 124872 KB Output is correct
36 Correct 488 ms 121508 KB Output is correct
37 Correct 621 ms 124552 KB Output is correct
38 Correct 517 ms 122876 KB Output is correct
39 Correct 873 ms 124852 KB Output is correct
40 Correct 516 ms 124600 KB Output is correct
41 Correct 1691 ms 124152 KB Output is correct
42 Correct 230 ms 114448 KB Output is correct
43 Correct 121 ms 110408 KB Output is correct
44 Correct 1048 ms 124404 KB Output is correct
45 Correct 1206 ms 124516 KB Output is correct
46 Correct 1682 ms 124184 KB Output is correct
47 Correct 1580 ms 124496 KB Output is correct
48 Correct 591 ms 124756 KB Output is correct
49 Correct 525 ms 120792 KB Output is correct
50 Correct 881 ms 120696 KB Output is correct
51 Correct 801 ms 136424 KB Output is correct
52 Correct 39 ms 93940 KB Output is correct
53 Correct 1626 ms 124080 KB Output is correct
54 Correct 984 ms 124256 KB Output is correct
55 Correct 1181 ms 124436 KB Output is correct
56 Correct 1642 ms 124180 KB Output is correct
57 Incorrect 741 ms 124528 KB Output isn't correct
58 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 744 ms 120832 KB Output is correct
2 Correct 746 ms 121984 KB Output is correct
3 Correct 515 ms 124672 KB Output is correct
4 Correct 586 ms 120020 KB Output is correct
5 Correct 38 ms 93972 KB Output is correct
6 Correct 785 ms 122024 KB Output is correct
7 Correct 195 ms 114380 KB Output is correct
8 Correct 124 ms 110416 KB Output is correct
9 Correct 520 ms 124624 KB Output is correct
10 Correct 906 ms 120888 KB Output is correct
11 Correct 499 ms 124820 KB Output is correct
12 Correct 38 ms 93840 KB Output is correct
13 Correct 39 ms 94036 KB Output is correct
14 Correct 38 ms 94036 KB Output is correct
15 Correct 38 ms 94044 KB Output is correct
16 Correct 38 ms 94040 KB Output is correct
17 Correct 44 ms 94288 KB Output is correct
18 Correct 45 ms 94036 KB Output is correct
19 Correct 38 ms 94032 KB Output is correct
20 Correct 38 ms 94032 KB Output is correct
21 Correct 38 ms 94036 KB Output is correct
22 Correct 38 ms 93816 KB Output is correct
23 Correct 38 ms 94044 KB Output is correct
24 Correct 38 ms 94000 KB Output is correct
25 Correct 39 ms 93916 KB Output is correct
26 Correct 43 ms 94028 KB Output is correct
27 Correct 42 ms 94044 KB Output is correct
28 Correct 41 ms 94024 KB Output is correct
29 Correct 42 ms 94036 KB Output is correct
30 Correct 48 ms 94032 KB Output is correct
31 Correct 46 ms 94020 KB Output is correct
32 Correct 47 ms 94032 KB Output is correct
33 Correct 52 ms 94036 KB Output is correct
34 Correct 48 ms 94160 KB Output is correct
35 Correct 456 ms 124872 KB Output is correct
36 Correct 488 ms 121508 KB Output is correct
37 Correct 621 ms 124552 KB Output is correct
38 Correct 517 ms 122876 KB Output is correct
39 Correct 873 ms 124852 KB Output is correct
40 Correct 516 ms 124600 KB Output is correct
41 Correct 1691 ms 124152 KB Output is correct
42 Correct 230 ms 114448 KB Output is correct
43 Correct 121 ms 110408 KB Output is correct
44 Correct 1048 ms 124404 KB Output is correct
45 Correct 1206 ms 124516 KB Output is correct
46 Correct 1682 ms 124184 KB Output is correct
47 Correct 1580 ms 124496 KB Output is correct
48 Correct 591 ms 124756 KB Output is correct
49 Correct 525 ms 120792 KB Output is correct
50 Correct 881 ms 120696 KB Output is correct
51 Correct 801 ms 136424 KB Output is correct
52 Correct 39 ms 93940 KB Output is correct
53 Correct 1626 ms 124080 KB Output is correct
54 Correct 984 ms 124256 KB Output is correct
55 Correct 1181 ms 124436 KB Output is correct
56 Correct 1642 ms 124180 KB Output is correct
57 Correct 2993 ms 228516 KB Output is correct
58 Correct 2674 ms 224368 KB Output is correct
59 Correct 4579 ms 224516 KB Output is correct
60 Correct 4137 ms 302540 KB Output is correct
61 Execution timed out 10043 ms 223312 KB Time limit exceeded
62 Halted 0 ms 0 KB -