oj.uz

Submission #165842

# Submission time Handle Problem Language Result Execution time Memory
165842 2019-11-29T09:58:42 Z choikiwon Two Dishes (JOI19_dishes) C++17
100 / 100
 7440 ms 502448 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2000010;

int N, M;
ll A[maxn], B[maxn], S[maxn], T[maxn], P[maxn], Q[maxn], nA[maxn], nB[maxn], nS[maxn], nT[maxn], nP[maxn], nQ[maxn];
int X[maxn], Y[maxn], inv[maxn], pnt[maxn];
pii ord[maxn];

vector<int> adj1[maxn], adj2[maxn];
ll dp[maxn];
ll offset;

struct BIT {
    ll tree[4 * maxn];
    ll lazy[4 * maxn];
    void init() {
        for(int i = 0; i < 4 * N; i++) {
            tree[i] = -1e17;
            lazy[i] = 0;
        }
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[n << 1] += lazy[n];
            lazy[n << 1] += lazy[n];
            tree[(n << 1) + 1] += lazy[n];
            lazy[(n << 1) + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, ll d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, n << 1);
        upd(a, b, d, m + 1, r, (n << 1) + 1);
        tree[n] = max(tree[n << 1], tree[(n << 1) + 1]);
    }
    void upd2(int x, ll v, int l, int r, int n) {
        if(x < l || r < x) return;
        if(l == r) {
            tree[n] = v;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd2(x, v, l, m, n << 1);
        upd2(x, v, m + 1, r, (n << 1) + 1);
        tree[n] = max(tree[n << 1], tree[(n << 1) + 1]);
    }
    ll quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return -1e18;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        ll L = quer(a, b, l, m, n << 1);
        ll R = quer(a, b, m + 1, r, (n << 1) + 1);
        return max(L, R);
    }
} bit;

void proc() {
    for(int i = 0; i < N; i++) {
        if(A[i] > S[i]) P[i] = 0;

        int s = 0, e = M - 1, p = M;
        while(s <= e) {
            int m = (s + e)>>1;

            if(A[i] + B[m] > S[i]) {
                p = m;
                e = m - 1;
            }
            else s = m + 1;
        }
        X[i] = p;
    }
    for(int i = 0; i < M; i++) {
        if(B[i] > T[i]) Q[i] = 0;

        int s = 0, e = N - 1, p = N;
        while(s <= e) {
            int m = (s + e)>>1;

            if(B[i] + A[m] > T[i]) {
                p = m;
                e = m - 1;
            }
            else s = m + 1;
        }
        Y[i] = p;
    }

    for(int i = 0; i < M; i++) adj1[i].clear();
    for(int i = 0; i < N; i++) adj2[i].clear();
    for(int i = 0; i < N; i++) adj1[ X[i] ].push_back(i);
    for(int i = 0; i < M; i++) adj2[ Y[i] ].push_back(i);
}

int main() {
    scanf("%d %d", &N, &M);

    for(int i = 0; i < N; i++) {
        scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
    }
    for(int i = 0; i < M; i++) {
        scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
    }

    for(int i = 1; i < N; i++) A[i] += A[i - 1];
    for(int i = 1; i < M; i++) B[i] += B[i - 1];

    proc();

    for(int i = 0; i < N; i++) if(P[i] < 0) offset += P[i];
    for(int i = 0; i < M; i++) if(Q[i] < 0) offset += Q[i];

    int cnt1 = 0;
    int cnt2 = 0;

    for(int i = 0; i < N; i++) {
        if(P[i] >= 0) {
            nA[cnt1] = A[i];
            nS[cnt1] = S[i];
            nP[cnt1] = P[i];
            cnt1++;
        }
        else {
            nA[cnt1] = A[i];
            nS[cnt1] = S[i];
            nP[cnt1] = 0;
            cnt1++;
        }

        for(int j = 0; j < adj2[i].size(); j++) {
            int k = adj2[i][j];

            if(Q[k] < 0) {
                nA[cnt1] = A[i];
                nS[cnt1] = A[i] + B[k] - 1;
                nP[cnt1] = -Q[k];
                cnt1++;
            }
        }
    }
    for(int i = 0; i < M; i++) {
        if(Q[i] >= 0) {
            nB[cnt2] = B[i];
            nT[cnt2] = T[i];
            nQ[cnt2] = Q[i];
            cnt2++;
        }
        else {
            nB[cnt2] = B[i];
            nT[cnt2] = T[i];
            nQ[cnt2] = 0;
            cnt2++;
        }

        for(int j = 0; j < adj1[i].size(); j++) {
            int k = adj1[i][j];

            if(P[k] < 0) {
                nB[cnt2] = B[i];
                nT[cnt2] = B[i] + A[k] - 1;
                nQ[cnt2] = -P[k];
                cnt2++;
            }
        }
    }

    N = cnt1;
    M = cnt2;
    for(int i = 0; i < N; i++) {
        A[i] = nA[i];
        S[i] = nS[i];
        P[i] = nP[i];
    }
    for(int i = 0; i < M; i++) {
        B[i] = nB[i];
        T[i] = nT[i];
        Q[i] = nQ[i];
    }

    proc();

    //*/

    for(int i = 0; i < N; i++) ord[i] = pii(X[i], -i);
    sort(ord, ord + N);
    for(int i = 0; i < N; i++) inv[ -ord[i].second ] = i;
    int pos = 0;
    for(int i = 0; i < M; i++) {
        while(pos < N && ord[pos].first <= i) pos++;
        pnt[i] = pos - 1;
    }

    for(int i = 0; i < M; i++) offset += Q[i];

    bit.init();
    for(int i = N - 1; i >= 0; i--) {
        dp[i] = bit.quer(inv[i] + 1, N - 1, 0, N - 1, 1);
        dp[i] = max(0LL, dp[i]);

        bit.upd2(inv[i], dp[i], 0, N - 1, 1);
        bit.upd(0, inv[i], P[i], 0, N - 1, 1);

        for(int j = 0; j < adj2[i].size(); j++) {
            int k = adj2[i][j];

            bit.upd(0, pnt[k], -Q[k], 0, N - 1, 1);
        }
    }

    ll ans = bit.quer(0, N - 1, 0, N - 1, 1);
    ans = max(0LL, ans);

    printf("%lld", ans + offset);
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:145:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj2[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:170:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj1[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:218:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj2[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~
dishes.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
dishes.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &A[i], &S[i], &P[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &B[i], &T[i], &Q[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 139936 KB Output is correct
2 Correct 551 ms 147952 KB Output is correct
3 Correct 517 ms 148436 KB Output is correct
4 Correct 521 ms 151772 KB Output is correct
5 Correct 93 ms 94456 KB Output is correct
6 Correct 532 ms 146164 KB Output is correct
7 Correct 207 ms 113892 KB Output is correct
8 Correct 329 ms 129764 KB Output is correct
9 Correct 479 ms 139564 KB Output is correct
10 Correct 505 ms 150904 KB Output is correct
11 Correct 411 ms 141400 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 94460 KB Output is correct
2 Correct 92 ms 94428 KB Output is correct
3 Correct 94 ms 94456 KB Output is correct
4 Correct 94 ms 94456 KB Output is correct
5 Correct 94 ms 94584 KB Output is correct
6 Correct 93 ms 94456 KB Output is correct
7 Correct 93 ms 94456 KB Output is correct
8 Correct 95 ms 94452 KB Output is correct
9 Correct 94 ms 94456 KB Output is correct
10 Correct 93 ms 94476 KB Output is correct
11 Correct 93 ms 94456 KB Output is correct
12 Correct 131 ms 94384 KB Output is correct
13 Correct 95 ms 94460 KB Output is correct
14 Correct 94 ms 94432 KB Output is correct
15 Correct 95 ms 94456 KB Output is correct
16 Correct 93 ms 94456 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 94460 KB Output is correct
2 Correct 92 ms 94428 KB Output is correct
3 Correct 94 ms 94456 KB Output is correct
4 Correct 94 ms 94456 KB Output is correct
5 Correct 94 ms 94584 KB Output is correct
6 Correct 93 ms 94456 KB Output is correct
7 Correct 93 ms 94456 KB Output is correct
8 Correct 95 ms 94452 KB Output is correct
9 Correct 94 ms 94456 KB Output is correct
10 Correct 93 ms 94476 KB Output is correct
11 Correct 93 ms 94456 KB Output is correct
12 Correct 131 ms 94384 KB Output is correct
13 Correct 95 ms 94460 KB Output is correct
14 Correct 94 ms 94432 KB Output is correct
15 Correct 95 ms 94456 KB Output is correct
16 Correct 93 ms 94456 KB Output is correct
17 Correct 100 ms 94924 KB Output is correct
18 Correct 97 ms 94960 KB Output is correct
19 Correct 98 ms 94968 KB Output is correct
20 Correct 97 ms 94968 KB Output is correct
21 Correct 97 ms 94860 KB Output is correct
22 Correct 97 ms 94972 KB Output is correct
23 Correct 100 ms 94968 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 94460 KB Output is correct
2 Correct 92 ms 94428 KB Output is correct
3 Correct 94 ms 94456 KB Output is correct
4 Correct 94 ms 94456 KB Output is correct
5 Correct 94 ms 94584 KB Output is correct
6 Correct 93 ms 94456 KB Output is correct
7 Correct 93 ms 94456 KB Output is correct
8 Correct 95 ms 94452 KB Output is correct
9 Correct 94 ms 94456 KB Output is correct
10 Correct 93 ms 94476 KB Output is correct
11 Correct 93 ms 94456 KB Output is correct
12 Correct 131 ms 94384 KB Output is correct
13 Correct 95 ms 94460 KB Output is correct
14 Correct 94 ms 94432 KB Output is correct
15 Correct 95 ms 94456 KB Output is correct
16 Correct 93 ms 94456 KB Output is correct
17 Correct 100 ms 94924 KB Output is correct
18 Correct 97 ms 94960 KB Output is correct
19 Correct 98 ms 94968 KB Output is correct
20 Correct 97 ms 94968 KB Output is correct
21 Correct 97 ms 94860 KB Output is correct
22 Correct 97 ms 94972 KB Output is correct
23 Correct 100 ms 94968 KB Output is correct
24 Correct 451 ms 140752 KB Output is correct
25 Correct 512 ms 139116 KB Output is correct
26 Correct 511 ms 150260 KB Output is correct
27 Correct 540 ms 150140 KB Output is correct
28 Correct 607 ms 141304 KB Output is correct
29 Correct 435 ms 138704 KB Output is correct
30 Correct 892 ms 150776 KB Output is correct
31 Correct 204 ms 111972 KB Output is correct
32 Correct 339 ms 127688 KB Output is correct
33 Correct 733 ms 147572 KB Output is correct
34 Correct 738 ms 147824 KB Output is correct
35 Correct 819 ms 144120 KB Output is correct
36 Correct 817 ms 142968 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 94460 KB Output is correct
2 Correct 92 ms 94428 KB Output is correct
3 Correct 94 ms 94456 KB Output is correct
4 Correct 94 ms 94456 KB Output is correct
5 Correct 94 ms 94584 KB Output is correct
6 Correct 93 ms 94456 KB Output is correct
7 Correct 93 ms 94456 KB Output is correct
8 Correct 95 ms 94452 KB Output is correct
9 Correct 94 ms 94456 KB Output is correct
10 Correct 93 ms 94476 KB Output is correct
11 Correct 93 ms 94456 KB Output is correct
12 Correct 131 ms 94384 KB Output is correct
13 Correct 95 ms 94460 KB Output is correct
14 Correct 94 ms 94432 KB Output is correct
15 Correct 95 ms 94456 KB Output is correct
16 Correct 93 ms 94456 KB Output is correct
17 Correct 100 ms 94924 KB Output is correct
18 Correct 97 ms 94960 KB Output is correct
19 Correct 98 ms 94968 KB Output is correct
20 Correct 97 ms 94968 KB Output is correct
21 Correct 97 ms 94860 KB Output is correct
22 Correct 97 ms 94972 KB Output is correct
23 Correct 100 ms 94968 KB Output is correct
24 Correct 451 ms 140752 KB Output is correct
25 Correct 512 ms 139116 KB Output is correct
26 Correct 511 ms 150260 KB Output is correct
27 Correct 540 ms 150140 KB Output is correct
28 Correct 607 ms 141304 KB Output is correct
29 Correct 435 ms 138704 KB Output is correct
30 Correct 892 ms 150776 KB Output is correct
31 Correct 204 ms 111972 KB Output is correct
32 Correct 339 ms 127688 KB Output is correct
33 Correct 733 ms 147572 KB Output is correct
34 Correct 738 ms 147824 KB Output is correct
35 Correct 819 ms 144120 KB Output is correct
36 Correct 817 ms 142968 KB Output is correct
37 Correct 534 ms 144816 KB Output is correct
38 Correct 578 ms 147048 KB Output is correct
39 Correct 551 ms 147792 KB Output is correct
40 Correct 549 ms 147712 KB Output is correct
41 Correct 94 ms 94456 KB Output is correct
42 Correct 948 ms 146156 KB Output is correct
43 Correct 764 ms 139888 KB Output is correct
44 Correct 731 ms 140016 KB Output is correct
45 Correct 869 ms 142328 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 94460 KB Output is correct
2 Correct 92 ms 94428 KB Output is correct
3 Correct 94 ms 94456 KB Output is correct
4 Correct 94 ms 94456 KB Output is correct
5 Correct 94 ms 94584 KB Output is correct
6 Correct 93 ms 94456 KB Output is correct
7 Correct 93 ms 94456 KB Output is correct
8 Correct 95 ms 94452 KB Output is correct
9 Correct 94 ms 94456 KB Output is correct
10 Correct 93 ms 94476 KB Output is correct
11 Correct 93 ms 94456 KB Output is correct
12 Correct 131 ms 94384 KB Output is correct
13 Correct 95 ms 94460 KB Output is correct
14 Correct 94 ms 94432 KB Output is correct
15 Correct 95 ms 94456 KB Output is correct
16 Correct 93 ms 94456 KB Output is correct
17 Correct 100 ms 94924 KB Output is correct
18 Correct 97 ms 94960 KB Output is correct
19 Correct 98 ms 94968 KB Output is correct
20 Correct 97 ms 94968 KB Output is correct
21 Correct 97 ms 94860 KB Output is correct
22 Correct 97 ms 94972 KB Output is correct
23 Correct 100 ms 94968 KB Output is correct
24 Correct 451 ms 140752 KB Output is correct
25 Correct 512 ms 139116 KB Output is correct
26 Correct 511 ms 150260 KB Output is correct
27 Correct 540 ms 150140 KB Output is correct
28 Correct 607 ms 141304 KB Output is correct
29 Correct 435 ms 138704 KB Output is correct
30 Correct 892 ms 150776 KB Output is correct
31 Correct 204 ms 111972 KB Output is correct
32 Correct 339 ms 127688 KB Output is correct
33 Correct 733 ms 147572 KB Output is correct
34 Correct 738 ms 147824 KB Output is correct
35 Correct 819 ms 144120 KB Output is correct
36 Correct 817 ms 142968 KB Output is correct
37 Correct 534 ms 144816 KB Output is correct
38 Correct 578 ms 147048 KB Output is correct
39 Correct 551 ms 147792 KB Output is correct
40 Correct 549 ms 147712 KB Output is correct
41 Correct 94 ms 94456 KB Output is correct
42 Correct 948 ms 146156 KB Output is correct
43 Correct 764 ms 139888 KB Output is correct
44 Correct 731 ms 140016 KB Output is correct
45 Correct 869 ms 142328 KB Output is correct
46 Correct 2438 ms 326652 KB Output is correct
47 Correct 2648 ms 328432 KB Output is correct
48 Correct 2540 ms 348112 KB Output is correct
49 Correct 2532 ms 352924 KB Output is correct
50 Correct 5673 ms 330248 KB Output is correct
51 Correct 3937 ms 306916 KB Output is correct
52 Correct 3986 ms 306140 KB Output is correct
53 Correct 5068 ms 323312 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 139936 KB Output is correct
2 Correct 551 ms 147952 KB Output is correct
3 Correct 517 ms 148436 KB Output is correct
4 Correct 521 ms 151772 KB Output is correct
5 Correct 93 ms 94456 KB Output is correct
6 Correct 532 ms 146164 KB Output is correct
7 Correct 207 ms 113892 KB Output is correct
8 Correct 329 ms 129764 KB Output is correct
9 Correct 479 ms 139564 KB Output is correct
10 Correct 505 ms 150904 KB Output is correct
11 Correct 411 ms 141400 KB Output is correct
12 Correct 92 ms 94460 KB Output is correct
13 Correct 92 ms 94428 KB Output is correct
14 Correct 94 ms 94456 KB Output is correct
15 Correct 94 ms 94456 KB Output is correct
16 Correct 94 ms 94584 KB Output is correct
17 Correct 93 ms 94456 KB Output is correct
18 Correct 93 ms 94456 KB Output is correct
19 Correct 95 ms 94452 KB Output is correct
20 Correct 94 ms 94456 KB Output is correct
21 Correct 93 ms 94476 KB Output is correct
22 Correct 93 ms 94456 KB Output is correct
23 Correct 131 ms 94384 KB Output is correct
24 Correct 95 ms 94460 KB Output is correct
25 Correct 94 ms 94432 KB Output is correct
26 Correct 95 ms 94456 KB Output is correct
27 Correct 93 ms 94456 KB Output is correct
28 Correct 100 ms 94924 KB Output is correct
29 Correct 97 ms 94960 KB Output is correct
30 Correct 98 ms 94968 KB Output is correct
31 Correct 97 ms 94968 KB Output is correct
32 Correct 97 ms 94860 KB Output is correct
33 Correct 97 ms 94972 KB Output is correct
34 Correct 100 ms 94968 KB Output is correct
35 Correct 451 ms 140752 KB Output is correct
36 Correct 512 ms 139116 KB Output is correct
37 Correct 511 ms 150260 KB Output is correct
38 Correct 540 ms 150140 KB Output is correct
39 Correct 607 ms 141304 KB Output is correct
40 Correct 435 ms 138704 KB Output is correct
41 Correct 892 ms 150776 KB Output is correct
42 Correct 204 ms 111972 KB Output is correct
43 Correct 339 ms 127688 KB Output is correct
44 Correct 733 ms 147572 KB Output is correct
45 Correct 738 ms 147824 KB Output is correct
46 Correct 819 ms 144120 KB Output is correct
47 Correct 817 ms 142968 KB Output is correct
48 Correct 534 ms 144816 KB Output is correct
49 Correct 578 ms 147048 KB Output is correct
50 Correct 551 ms 147792 KB Output is correct
51 Correct 549 ms 147712 KB Output is correct
52 Correct 94 ms 94456 KB Output is correct
53 Correct 948 ms 146156 KB Output is correct
54 Correct 764 ms 139888 KB Output is correct
55 Correct 731 ms 140016 KB Output is correct
56 Correct 869 ms 142328 KB Output is correct
57 Correct 640 ms 164452 KB Output is correct
58 Correct 825 ms 175812 KB Output is correct
59 Correct 762 ms 179320 KB Output is correct
60 Correct 649 ms 160908 KB Output is correct
61 Correct 919 ms 142244 KB Output is correct
62 Correct 95 ms 94328 KB Output is correct
63 Correct 1127 ms 157648 KB Output is correct
64 Correct 845 ms 146300 KB Output is correct
65 Correct 1004 ms 154240 KB Output is correct
66 Correct 1075 ms 159580 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 139936 KB Output is correct
2 Correct 551 ms 147952 KB Output is correct
3 Correct 517 ms 148436 KB Output is correct
4 Correct 521 ms 151772 KB Output is correct
5 Correct 93 ms 94456 KB Output is correct
6 Correct 532 ms 146164 KB Output is correct
7 Correct 207 ms 113892 KB Output is correct
8 Correct 329 ms 129764 KB Output is correct
9 Correct 479 ms 139564 KB Output is correct
10 Correct 505 ms 150904 KB Output is correct
11 Correct 411 ms 141400 KB Output is correct
12 Correct 92 ms 94460 KB Output is correct
13 Correct 92 ms 94428 KB Output is correct
14 Correct 94 ms 94456 KB Output is correct
15 Correct 94 ms 94456 KB Output is correct
16 Correct 94 ms 94584 KB Output is correct
17 Correct 93 ms 94456 KB Output is correct
18 Correct 93 ms 94456 KB Output is correct
19 Correct 95 ms 94452 KB Output is correct
20 Correct 94 ms 94456 KB Output is correct
21 Correct 93 ms 94476 KB Output is correct
22 Correct 93 ms 94456 KB Output is correct
23 Correct 131 ms 94384 KB Output is correct
24 Correct 95 ms 94460 KB Output is correct
25 Correct 94 ms 94432 KB Output is correct
26 Correct 95 ms 94456 KB Output is correct
27 Correct 93 ms 94456 KB Output is correct
28 Correct 100 ms 94924 KB Output is correct
29 Correct 97 ms 94960 KB Output is correct
30 Correct 98 ms 94968 KB Output is correct
31 Correct 97 ms 94968 KB Output is correct
32 Correct 97 ms 94860 KB Output is correct
33 Correct 97 ms 94972 KB Output is correct
34 Correct 100 ms 94968 KB Output is correct
35 Correct 451 ms 140752 KB Output is correct
36 Correct 512 ms 139116 KB Output is correct
37 Correct 511 ms 150260 KB Output is correct
38 Correct 540 ms 150140 KB Output is correct
39 Correct 607 ms 141304 KB Output is correct
40 Correct 435 ms 138704 KB Output is correct
41 Correct 892 ms 150776 KB Output is correct
42 Correct 204 ms 111972 KB Output is correct
43 Correct 339 ms 127688 KB Output is correct
44 Correct 733 ms 147572 KB Output is correct
45 Correct 738 ms 147824 KB Output is correct
46 Correct 819 ms 144120 KB Output is correct
47 Correct 817 ms 142968 KB Output is correct
48 Correct 534 ms 144816 KB Output is correct
49 Correct 578 ms 147048 KB Output is correct
50 Correct 551 ms 147792 KB Output is correct
51 Correct 549 ms 147712 KB Output is correct
52 Correct 94 ms 94456 KB Output is correct
53 Correct 948 ms 146156 KB Output is correct
54 Correct 764 ms 139888 KB Output is correct
55 Correct 731 ms 140016 KB Output is correct
56 Correct 869 ms 142328 KB Output is correct
57 Correct 2438 ms 326652 KB Output is correct
58 Correct 2648 ms 328432 KB Output is correct
59 Correct 2540 ms 348112 KB Output is correct
60 Correct 2532 ms 352924 KB Output is correct
61 Correct 5673 ms 330248 KB Output is correct
62 Correct 3937 ms 306916 KB Output is correct
63 Correct 3986 ms 306140 KB Output is correct
64 Correct 5068 ms 323312 KB Output is correct
65 Correct 640 ms 164452 KB Output is correct
66 Correct 825 ms 175812 KB Output is correct
67 Correct 762 ms 179320 KB Output is correct
68 Correct 649 ms 160908 KB Output is correct
69 Correct 919 ms 142244 KB Output is correct
70 Correct 95 ms 94328 KB Output is correct
71 Correct 1127 ms 157648 KB Output is correct
72 Correct 845 ms 146300 KB Output is correct
73 Correct 1004 ms 154240 KB Output is correct
74 Correct 1075 ms 159580 KB Output is correct
75 Correct 2930 ms 423824 KB Output is correct
76 Correct 3841 ms 502448 KB Output is correct
77 Correct 3528 ms 497568 KB Output is correct
78 Correct 3027 ms 421380 KB Output is correct
79 Correct 7440 ms 407796 KB Output is correct
80 Correct 4685 ms 355108 KB Output is correct
81 Correct 5331 ms 367396 KB Output is correct
82 Correct 6715 ms 397780 KB Output is correct
83 Correct 6559 ms 400756 KB Output is correct