답안 #927759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927759 2024-02-15T10:02:54 Z boris_mihov Two Dishes (JOI19_dishes) C++17
65 / 100
10000 ms 366468 KB
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

#define int long long
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(long long int)':
dishes.cpp:216:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
  216 |     int nextVal = 0;
      |         ^~~~~~~
dishes.cpp: In constructor 'SegmentTree::Node::Node()':
dishes.cpp:77:21: warning: '*<unknown>.SegmentTree::Node::lazy' is used uninitialized in this function [-Wuninitialized]
   77 |             value = lazy;
      |                     ^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 762 ms 127648 KB Output is correct
2 Correct 762 ms 129884 KB Output is correct
3 Correct 493 ms 130296 KB Output is correct
4 Correct 573 ms 126584 KB Output is correct
5 Correct 34 ms 94032 KB Output is correct
6 Correct 848 ms 126628 KB Output is correct
7 Correct 165 ms 117960 KB Output is correct
8 Correct 148 ms 112456 KB Output is correct
9 Correct 530 ms 130252 KB Output is correct
10 Correct 915 ms 128096 KB Output is correct
11 Correct 455 ms 130248 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 94032 KB Output is correct
2 Correct 34 ms 93968 KB Output is correct
3 Correct 35 ms 94032 KB Output is correct
4 Correct 35 ms 94040 KB Output is correct
5 Correct 34 ms 94040 KB Output is correct
6 Correct 35 ms 94036 KB Output is correct
7 Correct 38 ms 94044 KB Output is correct
8 Correct 34 ms 94036 KB Output is correct
9 Correct 35 ms 94036 KB Output is correct
10 Correct 34 ms 94032 KB Output is correct
11 Correct 34 ms 93996 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 37 ms 94040 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 34 ms 94036 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 94032 KB Output is correct
2 Correct 34 ms 93968 KB Output is correct
3 Correct 35 ms 94032 KB Output is correct
4 Correct 35 ms 94040 KB Output is correct
5 Correct 34 ms 94040 KB Output is correct
6 Correct 35 ms 94036 KB Output is correct
7 Correct 38 ms 94044 KB Output is correct
8 Correct 34 ms 94036 KB Output is correct
9 Correct 35 ms 94036 KB Output is correct
10 Correct 34 ms 94032 KB Output is correct
11 Correct 34 ms 93996 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 37 ms 94040 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 34 ms 94036 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
17 Correct 37 ms 94040 KB Output is correct
18 Correct 37 ms 94296 KB Output is correct
19 Correct 43 ms 94036 KB Output is correct
20 Correct 40 ms 94032 KB Output is correct
21 Correct 41 ms 94036 KB Output is correct
22 Correct 43 ms 94044 KB Output is correct
23 Correct 43 ms 94036 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 94032 KB Output is correct
2 Correct 34 ms 93968 KB Output is correct
3 Correct 35 ms 94032 KB Output is correct
4 Correct 35 ms 94040 KB Output is correct
5 Correct 34 ms 94040 KB Output is correct
6 Correct 35 ms 94036 KB Output is correct
7 Correct 38 ms 94044 KB Output is correct
8 Correct 34 ms 94036 KB Output is correct
9 Correct 35 ms 94036 KB Output is correct
10 Correct 34 ms 94032 KB Output is correct
11 Correct 34 ms 93996 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 37 ms 94040 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 34 ms 94036 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
17 Correct 37 ms 94040 KB Output is correct
18 Correct 37 ms 94296 KB Output is correct
19 Correct 43 ms 94036 KB Output is correct
20 Correct 40 ms 94032 KB Output is correct
21 Correct 41 ms 94036 KB Output is correct
22 Correct 43 ms 94044 KB Output is correct
23 Correct 43 ms 94036 KB Output is correct
24 Correct 425 ms 130400 KB Output is correct
25 Correct 462 ms 129480 KB Output is correct
26 Correct 558 ms 133208 KB Output is correct
27 Correct 503 ms 132216 KB Output is correct
28 Correct 840 ms 133456 KB Output is correct
29 Correct 475 ms 130316 KB Output is correct
30 Correct 1645 ms 132056 KB Output is correct
31 Correct 200 ms 120164 KB Output is correct
32 Correct 114 ms 112492 KB Output is correct
33 Correct 968 ms 130100 KB Output is correct
34 Correct 1249 ms 128960 KB Output is correct
35 Correct 1696 ms 132232 KB Output is correct
36 Correct 1704 ms 131848 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 94032 KB Output is correct
2 Correct 34 ms 93968 KB Output is correct
3 Correct 35 ms 94032 KB Output is correct
4 Correct 35 ms 94040 KB Output is correct
5 Correct 34 ms 94040 KB Output is correct
6 Correct 35 ms 94036 KB Output is correct
7 Correct 38 ms 94044 KB Output is correct
8 Correct 34 ms 94036 KB Output is correct
9 Correct 35 ms 94036 KB Output is correct
10 Correct 34 ms 94032 KB Output is correct
11 Correct 34 ms 93996 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 37 ms 94040 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 34 ms 94036 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
17 Correct 37 ms 94040 KB Output is correct
18 Correct 37 ms 94296 KB Output is correct
19 Correct 43 ms 94036 KB Output is correct
20 Correct 40 ms 94032 KB Output is correct
21 Correct 41 ms 94036 KB Output is correct
22 Correct 43 ms 94044 KB Output is correct
23 Correct 43 ms 94036 KB Output is correct
24 Correct 425 ms 130400 KB Output is correct
25 Correct 462 ms 129480 KB Output is correct
26 Correct 558 ms 133208 KB Output is correct
27 Correct 503 ms 132216 KB Output is correct
28 Correct 840 ms 133456 KB Output is correct
29 Correct 475 ms 130316 KB Output is correct
30 Correct 1645 ms 132056 KB Output is correct
31 Correct 200 ms 120164 KB Output is correct
32 Correct 114 ms 112492 KB Output is correct
33 Correct 968 ms 130100 KB Output is correct
34 Correct 1249 ms 128960 KB Output is correct
35 Correct 1696 ms 132232 KB Output is correct
36 Correct 1704 ms 131848 KB Output is correct
37 Correct 581 ms 130236 KB Output is correct
38 Correct 569 ms 127616 KB Output is correct
39 Correct 988 ms 128148 KB Output is correct
40 Correct 851 ms 143836 KB Output is correct
41 Correct 37 ms 94036 KB Output is correct
42 Correct 1846 ms 131928 KB Output is correct
43 Correct 1130 ms 130196 KB Output is correct
44 Correct 1368 ms 128964 KB Output is correct
45 Correct 1756 ms 131992 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 94032 KB Output is correct
2 Correct 34 ms 93968 KB Output is correct
3 Correct 35 ms 94032 KB Output is correct
4 Correct 35 ms 94040 KB Output is correct
5 Correct 34 ms 94040 KB Output is correct
6 Correct 35 ms 94036 KB Output is correct
7 Correct 38 ms 94044 KB Output is correct
8 Correct 34 ms 94036 KB Output is correct
9 Correct 35 ms 94036 KB Output is correct
10 Correct 34 ms 94032 KB Output is correct
11 Correct 34 ms 93996 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 37 ms 94040 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 34 ms 94036 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
17 Correct 37 ms 94040 KB Output is correct
18 Correct 37 ms 94296 KB Output is correct
19 Correct 43 ms 94036 KB Output is correct
20 Correct 40 ms 94032 KB Output is correct
21 Correct 41 ms 94036 KB Output is correct
22 Correct 43 ms 94044 KB Output is correct
23 Correct 43 ms 94036 KB Output is correct
24 Correct 425 ms 130400 KB Output is correct
25 Correct 462 ms 129480 KB Output is correct
26 Correct 558 ms 133208 KB Output is correct
27 Correct 503 ms 132216 KB Output is correct
28 Correct 840 ms 133456 KB Output is correct
29 Correct 475 ms 130316 KB Output is correct
30 Correct 1645 ms 132056 KB Output is correct
31 Correct 200 ms 120164 KB Output is correct
32 Correct 114 ms 112492 KB Output is correct
33 Correct 968 ms 130100 KB Output is correct
34 Correct 1249 ms 128960 KB Output is correct
35 Correct 1696 ms 132232 KB Output is correct
36 Correct 1704 ms 131848 KB Output is correct
37 Correct 581 ms 130236 KB Output is correct
38 Correct 569 ms 127616 KB Output is correct
39 Correct 988 ms 128148 KB Output is correct
40 Correct 851 ms 143836 KB Output is correct
41 Correct 37 ms 94036 KB Output is correct
42 Correct 1846 ms 131928 KB Output is correct
43 Correct 1130 ms 130196 KB Output is correct
44 Correct 1368 ms 128964 KB Output is correct
45 Correct 1756 ms 131992 KB Output is correct
46 Correct 3064 ms 264224 KB Output is correct
47 Correct 2684 ms 292540 KB Output is correct
48 Correct 4745 ms 288100 KB Output is correct
49 Correct 4172 ms 366468 KB Output is correct
50 Execution timed out 10110 ms 292272 KB Time limit exceeded
51 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 762 ms 127648 KB Output is correct
2 Correct 762 ms 129884 KB Output is correct
3 Correct 493 ms 130296 KB Output is correct
4 Correct 573 ms 126584 KB Output is correct
5 Correct 34 ms 94032 KB Output is correct
6 Correct 848 ms 126628 KB Output is correct
7 Correct 165 ms 117960 KB Output is correct
8 Correct 148 ms 112456 KB Output is correct
9 Correct 530 ms 130252 KB Output is correct
10 Correct 915 ms 128096 KB Output is correct
11 Correct 455 ms 130248 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 34 ms 93968 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
17 Correct 35 ms 94036 KB Output is correct
18 Correct 38 ms 94044 KB Output is correct
19 Correct 34 ms 94036 KB Output is correct
20 Correct 35 ms 94036 KB Output is correct
21 Correct 34 ms 94032 KB Output is correct
22 Correct 34 ms 93996 KB Output is correct
23 Correct 35 ms 94032 KB Output is correct
24 Correct 37 ms 94040 KB Output is correct
25 Correct 35 ms 94032 KB Output is correct
26 Correct 34 ms 94036 KB Output is correct
27 Correct 34 ms 94040 KB Output is correct
28 Correct 37 ms 94040 KB Output is correct
29 Correct 37 ms 94296 KB Output is correct
30 Correct 43 ms 94036 KB Output is correct
31 Correct 40 ms 94032 KB Output is correct
32 Correct 41 ms 94036 KB Output is correct
33 Correct 43 ms 94044 KB Output is correct
34 Correct 43 ms 94036 KB Output is correct
35 Correct 425 ms 130400 KB Output is correct
36 Correct 462 ms 129480 KB Output is correct
37 Correct 558 ms 133208 KB Output is correct
38 Correct 503 ms 132216 KB Output is correct
39 Correct 840 ms 133456 KB Output is correct
40 Correct 475 ms 130316 KB Output is correct
41 Correct 1645 ms 132056 KB Output is correct
42 Correct 200 ms 120164 KB Output is correct
43 Correct 114 ms 112492 KB Output is correct
44 Correct 968 ms 130100 KB Output is correct
45 Correct 1249 ms 128960 KB Output is correct
46 Correct 1696 ms 132232 KB Output is correct
47 Correct 1704 ms 131848 KB Output is correct
48 Correct 581 ms 130236 KB Output is correct
49 Correct 569 ms 127616 KB Output is correct
50 Correct 988 ms 128148 KB Output is correct
51 Correct 851 ms 143836 KB Output is correct
52 Correct 37 ms 94036 KB Output is correct
53 Correct 1846 ms 131928 KB Output is correct
54 Correct 1130 ms 130196 KB Output is correct
55 Correct 1368 ms 128964 KB Output is correct
56 Correct 1756 ms 131992 KB Output is correct
57 Incorrect 688 ms 140604 KB Output isn't correct
58 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 762 ms 127648 KB Output is correct
2 Correct 762 ms 129884 KB Output is correct
3 Correct 493 ms 130296 KB Output is correct
4 Correct 573 ms 126584 KB Output is correct
5 Correct 34 ms 94032 KB Output is correct
6 Correct 848 ms 126628 KB Output is correct
7 Correct 165 ms 117960 KB Output is correct
8 Correct 148 ms 112456 KB Output is correct
9 Correct 530 ms 130252 KB Output is correct
10 Correct 915 ms 128096 KB Output is correct
11 Correct 455 ms 130248 KB Output is correct
12 Correct 35 ms 94032 KB Output is correct
13 Correct 34 ms 93968 KB Output is correct
14 Correct 35 ms 94032 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 34 ms 94040 KB Output is correct
17 Correct 35 ms 94036 KB Output is correct
18 Correct 38 ms 94044 KB Output is correct
19 Correct 34 ms 94036 KB Output is correct
20 Correct 35 ms 94036 KB Output is correct
21 Correct 34 ms 94032 KB Output is correct
22 Correct 34 ms 93996 KB Output is correct
23 Correct 35 ms 94032 KB Output is correct
24 Correct 37 ms 94040 KB Output is correct
25 Correct 35 ms 94032 KB Output is correct
26 Correct 34 ms 94036 KB Output is correct
27 Correct 34 ms 94040 KB Output is correct
28 Correct 37 ms 94040 KB Output is correct
29 Correct 37 ms 94296 KB Output is correct
30 Correct 43 ms 94036 KB Output is correct
31 Correct 40 ms 94032 KB Output is correct
32 Correct 41 ms 94036 KB Output is correct
33 Correct 43 ms 94044 KB Output is correct
34 Correct 43 ms 94036 KB Output is correct
35 Correct 425 ms 130400 KB Output is correct
36 Correct 462 ms 129480 KB Output is correct
37 Correct 558 ms 133208 KB Output is correct
38 Correct 503 ms 132216 KB Output is correct
39 Correct 840 ms 133456 KB Output is correct
40 Correct 475 ms 130316 KB Output is correct
41 Correct 1645 ms 132056 KB Output is correct
42 Correct 200 ms 120164 KB Output is correct
43 Correct 114 ms 112492 KB Output is correct
44 Correct 968 ms 130100 KB Output is correct
45 Correct 1249 ms 128960 KB Output is correct
46 Correct 1696 ms 132232 KB Output is correct
47 Correct 1704 ms 131848 KB Output is correct
48 Correct 581 ms 130236 KB Output is correct
49 Correct 569 ms 127616 KB Output is correct
50 Correct 988 ms 128148 KB Output is correct
51 Correct 851 ms 143836 KB Output is correct
52 Correct 37 ms 94036 KB Output is correct
53 Correct 1846 ms 131928 KB Output is correct
54 Correct 1130 ms 130196 KB Output is correct
55 Correct 1368 ms 128964 KB Output is correct
56 Correct 1756 ms 131992 KB Output is correct
57 Correct 3064 ms 264224 KB Output is correct
58 Correct 2684 ms 292540 KB Output is correct
59 Correct 4745 ms 288100 KB Output is correct
60 Correct 4172 ms 366468 KB Output is correct
61 Execution timed out 10110 ms 292272 KB Time limit exceeded
62 Halted 0 ms 0 KB -