oj.uz

답안 #927762

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

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 818 ms 133552 KB Output is correct
2 Correct 733 ms 123464 KB Output is correct
3 Correct 547 ms 131004 KB Output is correct
4 Correct 580 ms 126116 KB Output is correct
5 Correct 34 ms 93884 KB Output is correct
6 Correct 769 ms 128184 KB Output is correct
7 Correct 183 ms 117700 KB Output is correct
8 Correct 125 ms 113592 KB Output is correct
9 Correct 503 ms 131320 KB Output is correct
10 Correct 906 ms 124552 KB Output is correct
11 Correct 504 ms 128260 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 94044 KB Output is correct
2 Correct 35 ms 93800 KB Output is correct
3 Correct 36 ms 94044 KB Output is correct
4 Correct 34 ms 94032 KB Output is correct
5 Correct 34 ms 94296 KB Output is correct
6 Correct 34 ms 93888 KB Output is correct
7 Correct 34 ms 93988 KB Output is correct
8 Correct 35 ms 94036 KB Output is correct
9 Correct 34 ms 94044 KB Output is correct
10 Correct 36 ms 94044 KB Output is correct
11 Correct 35 ms 93820 KB Output is correct
12 Correct 35 ms 94036 KB Output is correct
13 Correct 34 ms 94040 KB Output is correct
14 Correct 34 ms 93876 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 36 ms 94028 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 94044 KB Output is correct
2 Correct 35 ms 93800 KB Output is correct
3 Correct 36 ms 94044 KB Output is correct
4 Correct 34 ms 94032 KB Output is correct
5 Correct 34 ms 94296 KB Output is correct
6 Correct 34 ms 93888 KB Output is correct
7 Correct 34 ms 93988 KB Output is correct
8 Correct 35 ms 94036 KB Output is correct
9 Correct 34 ms 94044 KB Output is correct
10 Correct 36 ms 94044 KB Output is correct
11 Correct 35 ms 93820 KB Output is correct
12 Correct 35 ms 94036 KB Output is correct
13 Correct 34 ms 94040 KB Output is correct
14 Correct 34 ms 93876 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 36 ms 94028 KB Output is correct
17 Correct 38 ms 94180 KB Output is correct
18 Correct 39 ms 94032 KB Output is correct
19 Correct 44 ms 94032 KB Output is correct
20 Correct 40 ms 94200 KB Output is correct
21 Correct 42 ms 94288 KB Output is correct
22 Correct 44 ms 94008 KB Output is correct
23 Correct 44 ms 94036 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 94044 KB Output is correct
2 Correct 35 ms 93800 KB Output is correct
3 Correct 36 ms 94044 KB Output is correct
4 Correct 34 ms 94032 KB Output is correct
5 Correct 34 ms 94296 KB Output is correct
6 Correct 34 ms 93888 KB Output is correct
7 Correct 34 ms 93988 KB Output is correct
8 Correct 35 ms 94036 KB Output is correct
9 Correct 34 ms 94044 KB Output is correct
10 Correct 36 ms 94044 KB Output is correct
11 Correct 35 ms 93820 KB Output is correct
12 Correct 35 ms 94036 KB Output is correct
13 Correct 34 ms 94040 KB Output is correct
14 Correct 34 ms 93876 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 36 ms 94028 KB Output is correct
17 Correct 38 ms 94180 KB Output is correct
18 Correct 39 ms 94032 KB Output is correct
19 Correct 44 ms 94032 KB Output is correct
20 Correct 40 ms 94200 KB Output is correct
21 Correct 42 ms 94288 KB Output is correct
22 Correct 44 ms 94008 KB Output is correct
23 Correct 44 ms 94036 KB Output is correct
24 Correct 485 ms 130200 KB Output is correct
25 Correct 468 ms 122060 KB Output is correct
26 Correct 556 ms 124600 KB Output is correct
27 Correct 498 ms 122708 KB Output is correct
28 Correct 825 ms 124376 KB Output is correct
29 Correct 489 ms 129996 KB Output is correct
30 Correct 1570 ms 129084 KB Output is correct
31 Correct 211 ms 116748 KB Output is correct
32 Correct 117 ms 112960 KB Output is correct
33 Correct 1000 ms 128960 KB Output is correct
34 Correct 1139 ms 129320 KB Output is correct
35 Correct 1587 ms 126232 KB Output is correct
36 Correct 1593 ms 126164 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 94044 KB Output is correct
2 Correct 35 ms 93800 KB Output is correct
3 Correct 36 ms 94044 KB Output is correct
4 Correct 34 ms 94032 KB Output is correct
5 Correct 34 ms 94296 KB Output is correct
6 Correct 34 ms 93888 KB Output is correct
7 Correct 34 ms 93988 KB Output is correct
8 Correct 35 ms 94036 KB Output is correct
9 Correct 34 ms 94044 KB Output is correct
10 Correct 36 ms 94044 KB Output is correct
11 Correct 35 ms 93820 KB Output is correct
12 Correct 35 ms 94036 KB Output is correct
13 Correct 34 ms 94040 KB Output is correct
14 Correct 34 ms 93876 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 36 ms 94028 KB Output is correct
17 Correct 38 ms 94180 KB Output is correct
18 Correct 39 ms 94032 KB Output is correct
19 Correct 44 ms 94032 KB Output is correct
20 Correct 40 ms 94200 KB Output is correct
21 Correct 42 ms 94288 KB Output is correct
22 Correct 44 ms 94008 KB Output is correct
23 Correct 44 ms 94036 KB Output is correct
24 Correct 485 ms 130200 KB Output is correct
25 Correct 468 ms 122060 KB Output is correct
26 Correct 556 ms 124600 KB Output is correct
27 Correct 498 ms 122708 KB Output is correct
28 Correct 825 ms 124376 KB Output is correct
29 Correct 489 ms 129996 KB Output is correct
30 Correct 1570 ms 129084 KB Output is correct
31 Correct 211 ms 116748 KB Output is correct
32 Correct 117 ms 112960 KB Output is correct
33 Correct 1000 ms 128960 KB Output is correct
34 Correct 1139 ms 129320 KB Output is correct
35 Correct 1587 ms 126232 KB Output is correct
36 Correct 1593 ms 126164 KB Output is correct
37 Correct 592 ms 130724 KB Output is correct
38 Correct 507 ms 127060 KB Output is correct
39 Correct 924 ms 126032 KB Output is correct
40 Correct 768 ms 141516 KB Output is correct
41 Correct 48 ms 94032 KB Output is correct
42 Correct 1595 ms 130548 KB Output is correct
43 Correct 960 ms 130236 KB Output is correct
44 Correct 1215 ms 130456 KB Output is correct
45 Correct 1697 ms 127836 KB Output is correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 94044 KB Output is correct
2 Correct 35 ms 93800 KB Output is correct
3 Correct 36 ms 94044 KB Output is correct
4 Correct 34 ms 94032 KB Output is correct
5 Correct 34 ms 94296 KB Output is correct
6 Correct 34 ms 93888 KB Output is correct
7 Correct 34 ms 93988 KB Output is correct
8 Correct 35 ms 94036 KB Output is correct
9 Correct 34 ms 94044 KB Output is correct
10 Correct 36 ms 94044 KB Output is correct
11 Correct 35 ms 93820 KB Output is correct
12 Correct 35 ms 94036 KB Output is correct
13 Correct 34 ms 94040 KB Output is correct
14 Correct 34 ms 93876 KB Output is correct
15 Correct 35 ms 94040 KB Output is correct
16 Correct 36 ms 94028 KB Output is correct
17 Correct 38 ms 94180 KB Output is correct
18 Correct 39 ms 94032 KB Output is correct
19 Correct 44 ms 94032 KB Output is correct
20 Correct 40 ms 94200 KB Output is correct
21 Correct 42 ms 94288 KB Output is correct
22 Correct 44 ms 94008 KB Output is correct
23 Correct 44 ms 94036 KB Output is correct
24 Correct 485 ms 130200 KB Output is correct
25 Correct 468 ms 122060 KB Output is correct
26 Correct 556 ms 124600 KB Output is correct
27 Correct 498 ms 122708 KB Output is correct
28 Correct 825 ms 124376 KB Output is correct
29 Correct 489 ms 129996 KB Output is correct
30 Correct 1570 ms 129084 KB Output is correct
31 Correct 211 ms 116748 KB Output is correct
32 Correct 117 ms 112960 KB Output is correct
33 Correct 1000 ms 128960 KB Output is correct
34 Correct 1139 ms 129320 KB Output is correct
35 Correct 1587 ms 126232 KB Output is correct
36 Correct 1593 ms 126164 KB Output is correct
37 Correct 592 ms 130724 KB Output is correct
38 Correct 507 ms 127060 KB Output is correct
39 Correct 924 ms 126032 KB Output is correct
40 Correct 768 ms 141516 KB Output is correct
41 Correct 48 ms 94032 KB Output is correct
42 Correct 1595 ms 130548 KB Output is correct
43 Correct 960 ms 130236 KB Output is correct
44 Correct 1215 ms 130456 KB Output is correct
45 Correct 1697 ms 127836 KB Output is correct
46 Correct 2974 ms 237996 KB Output is correct
47 Correct 2575 ms 224712 KB Output is correct
48 Correct 4498 ms 224716 KB Output is correct
49 Correct 4009 ms 302896 KB Output is correct
50 Execution timed out 10020 ms 224396 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 818 ms 133552 KB Output is correct
2 Correct 733 ms 123464 KB Output is correct
3 Correct 547 ms 131004 KB Output is correct
4 Correct 580 ms 126116 KB Output is correct
5 Correct 34 ms 93884 KB Output is correct
6 Correct 769 ms 128184 KB Output is correct
7 Correct 183 ms 117700 KB Output is correct
8 Correct 125 ms 113592 KB Output is correct
9 Correct 503 ms 131320 KB Output is correct
10 Correct 906 ms 124552 KB Output is correct
11 Correct 504 ms 128260 KB Output is correct
12 Correct 34 ms 94044 KB Output is correct
13 Correct 35 ms 93800 KB Output is correct
14 Correct 36 ms 94044 KB Output is correct
15 Correct 34 ms 94032 KB Output is correct
16 Correct 34 ms 94296 KB Output is correct
17 Correct 34 ms 93888 KB Output is correct
18 Correct 34 ms 93988 KB Output is correct
19 Correct 35 ms 94036 KB Output is correct
20 Correct 34 ms 94044 KB Output is correct
21 Correct 36 ms 94044 KB Output is correct
22 Correct 35 ms 93820 KB Output is correct
23 Correct 35 ms 94036 KB Output is correct
24 Correct 34 ms 94040 KB Output is correct
25 Correct 34 ms 93876 KB Output is correct
26 Correct 35 ms 94040 KB Output is correct
27 Correct 36 ms 94028 KB Output is correct
28 Correct 38 ms 94180 KB Output is correct
29 Correct 39 ms 94032 KB Output is correct
30 Correct 44 ms 94032 KB Output is correct
31 Correct 40 ms 94200 KB Output is correct
32 Correct 42 ms 94288 KB Output is correct
33 Correct 44 ms 94008 KB Output is correct
34 Correct 44 ms 94036 KB Output is correct
35 Correct 485 ms 130200 KB Output is correct
36 Correct 468 ms 122060 KB Output is correct
37 Correct 556 ms 124600 KB Output is correct
38 Correct 498 ms 122708 KB Output is correct
39 Correct 825 ms 124376 KB Output is correct
40 Correct 489 ms 129996 KB Output is correct
41 Correct 1570 ms 129084 KB Output is correct
42 Correct 211 ms 116748 KB Output is correct
43 Correct 117 ms 112960 KB Output is correct
44 Correct 1000 ms 128960 KB Output is correct
45 Correct 1139 ms 129320 KB Output is correct
46 Correct 1587 ms 126232 KB Output is correct
47 Correct 1593 ms 126164 KB Output is correct
48 Correct 592 ms 130724 KB Output is correct
49 Correct 507 ms 127060 KB Output is correct
50 Correct 924 ms 126032 KB Output is correct
51 Correct 768 ms 141516 KB Output is correct
52 Correct 48 ms 94032 KB Output is correct
53 Correct 1595 ms 130548 KB Output is correct
54 Correct 960 ms 130236 KB Output is correct
55 Correct 1215 ms 130456 KB Output is correct
56 Correct 1697 ms 127836 KB Output is correct
57 Incorrect 686 ms 124608 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 818 ms 133552 KB Output is correct
2 Correct 733 ms 123464 KB Output is correct
3 Correct 547 ms 131004 KB Output is correct
4 Correct 580 ms 126116 KB Output is correct
5 Correct 34 ms 93884 KB Output is correct
6 Correct 769 ms 128184 KB Output is correct
7 Correct 183 ms 117700 KB Output is correct
8 Correct 125 ms 113592 KB Output is correct
9 Correct 503 ms 131320 KB Output is correct
10 Correct 906 ms 124552 KB Output is correct
11 Correct 504 ms 128260 KB Output is correct
12 Correct 34 ms 94044 KB Output is correct
13 Correct 35 ms 93800 KB Output is correct
14 Correct 36 ms 94044 KB Output is correct
15 Correct 34 ms 94032 KB Output is correct
16 Correct 34 ms 94296 KB Output is correct
17 Correct 34 ms 93888 KB Output is correct
18 Correct 34 ms 93988 KB Output is correct
19 Correct 35 ms 94036 KB Output is correct
20 Correct 34 ms 94044 KB Output is correct
21 Correct 36 ms 94044 KB Output is correct
22 Correct 35 ms 93820 KB Output is correct
23 Correct 35 ms 94036 KB Output is correct
24 Correct 34 ms 94040 KB Output is correct
25 Correct 34 ms 93876 KB Output is correct
26 Correct 35 ms 94040 KB Output is correct
27 Correct 36 ms 94028 KB Output is correct
28 Correct 38 ms 94180 KB Output is correct
29 Correct 39 ms 94032 KB Output is correct
30 Correct 44 ms 94032 KB Output is correct
31 Correct 40 ms 94200 KB Output is correct
32 Correct 42 ms 94288 KB Output is correct
33 Correct 44 ms 94008 KB Output is correct
34 Correct 44 ms 94036 KB Output is correct
35 Correct 485 ms 130200 KB Output is correct
36 Correct 468 ms 122060 KB Output is correct
37 Correct 556 ms 124600 KB Output is correct
38 Correct 498 ms 122708 KB Output is correct
39 Correct 825 ms 124376 KB Output is correct
40 Correct 489 ms 129996 KB Output is correct
41 Correct 1570 ms 129084 KB Output is correct
42 Correct 211 ms 116748 KB Output is correct
43 Correct 117 ms 112960 KB Output is correct
44 Correct 1000 ms 128960 KB Output is correct
45 Correct 1139 ms 129320 KB Output is correct
46 Correct 1587 ms 126232 KB Output is correct
47 Correct 1593 ms 126164 KB Output is correct
48 Correct 592 ms 130724 KB Output is correct
49 Correct 507 ms 127060 KB Output is correct
50 Correct 924 ms 126032 KB Output is correct
51 Correct 768 ms 141516 KB Output is correct
52 Correct 48 ms 94032 KB Output is correct
53 Correct 1595 ms 130548 KB Output is correct
54 Correct 960 ms 130236 KB Output is correct
55 Correct 1215 ms 130456 KB Output is correct
56 Correct 1697 ms 127836 KB Output is correct
57 Correct 2974 ms 237996 KB Output is correct
58 Correct 2575 ms 224712 KB Output is correct
59 Correct 4498 ms 224716 KB Output is correct
60 Correct 4009 ms 302896 KB Output is correct
61 Execution timed out 10020 ms 224396 KB Time limit exceeded
62 Halted 0 ms 0 KB -