oj.uz

Submission #292002

# Submission time Handle Problem Language Result Execution time Memory
292002 2020-09-06T07:30:35 Z Diuven Robogolf (ROI19_golf) C++11
100 / 100
 1743 ms 71372 KB 
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <iomanip>
#include <time.h>
#include <math.h>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#pragma comment(linker, "/STACK:256000000")

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef gp_hash_table<int, int> table;

const int INF = 1000 * 1000 * 1000 + 21;
const ll LLINF = (1ll << 60) + 5;
const int MOD = 998244353;

const int MAX_N = 1000 * 1000 + 228;

struct point {
    int x;
    int y;
};

bool operator<(const point& a, const point& b) {
    return a.x + a.y > b.x + b.y || (a.x + a.y == b.x + b.y && a.x - a.y < b.x - b.y);
}

bool operator==(const point& a, const point& b) {
    return a.x == b.x && a.y == b.y;
}

ll n, m;
int k;
map<pair<int, int>, int> costs;
vector<point> points[2];
vector<int> diags[2];
table dp;

inline int calc_cost(int x, int ptr1, int ptr2, map<pair<int, int>, int>::iterator it) {
    if (x == n - 1) {
        return 0;
    } else if (it != costs.end()) {
        return it->second;
    } else {
        int ans = -INF;
        if (1 <= ptr1 && ptr1 <= n + n - 1) {
            ans = max(ans, dp[ptr1]);
        } else {
            ans = max(ans, 0);
        }
        if (1 <= ptr2 && ptr2 <= n + n - 1) {
            ans = max(ans, dp[ptr2]);
        } else {
            ans = max(ans, 0);
        }

        return ans;
    }
}

int main() {
#ifdef CH_EGOR
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#else
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif

    scanf("%lld%lld%d", &n, &m, &k);
    n = max(n, m); // magic

    for (int i = -2; i <= k; ++i) {
        int x, y, c;
        if (i == -2) {
            x = 0;
            y = 1;
            c = 0;
        } else if (i == -1) {
            x = 1;
            y = 0;
            c = 0;
        } else if (i == 0) {
            x = 0;
            y = 0;
            c = 0;
        } else {
            scanf("%d%d%d", &x, &y, &c);
            --x; --y;
            costs[{x, y}] = c;
        }
        for (int dx = 0; dx <= 2; ++dx) {
            for (int dy = 0; dy <= 2; ++dy) {
                int gox = x - dx;
                int goy = y - dy;
                if (gox >= 0 && goy >= 0 && dx + dy <= 2) {
                    points[(gox + goy) & 1].push_back({gox, goy});
                    diags[(gox + goy) & 1].push_back(gox + goy);

                    if (gox - goy >= 0) {
                        points[(gox + goy) & 1].push_back({gox - goy, 0});
                        diags[(gox + goy) & 1].push_back({gox - goy});
                    } else {
                        points[(gox + goy) & 1].push_back({0, goy - gox});
                        diags[(gox + goy) & 1].push_back(goy - gox);
                    }

                    if (gox - goy >= 2) {
                        points[(gox + goy) & 1].push_back({gox - goy - 2, 0});
                        diags[(gox + goy) & 1].push_back({gox - goy - 2});
                    } else if (gox - goy <= -2) {
                        points[(gox + goy) & 1].push_back({0, goy - gox - 2});
                        diags[(gox + goy) & 1].push_back(goy - gox - 2);
                    }
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < 2; ++i) {
        dp.clear();
        sort(points[i].begin(), points[i].end());
        points[i].resize(unique(points[i].begin(), points[i].end()) - points[i].begin());
        sort(diags[i].begin(), diags[i].end());
        diags[i].resize(unique(diags[i].begin(), diags[i].end()) - diags[i].begin());
        reverse(diags[i].begin(), diags[i].end());

        int cur_add = 0;
        int points_ptr = 0;
        for (int j = 0; j < (int)diags[i].size(); ++j) {
            int lf = 0;
            int rf = 0;

            if (diags[i][j] >= n - 1) {
                lf = n - ((n + n - 2) - diags[i][j]);
                rf = n + ((n + n - 2) - diags[i][j]);
            } else {
                lf = n - diags[i][j];
                rf = n + diags[i][j];
            }

            if (j != 0) {
                ans = (ans + (ll)(diags[i][j - 1] - diags[i][j] - 1) / 2ll * cur_add) % MOD;
            }

            if (diags[i][j] < n - 1) {
                if (dp.find(lf - 2) != dp.end()) {
                    cur_add = (cur_add - dp[lf - 2]) % MOD;
                }
                if (dp.find(rf + 2) != dp.end()) {
                    cur_add = (cur_add - dp[rf + 2]) % MOD;
                }
            }

            vector<pair<int, int>> new_vals;
            for ( ;
                points_ptr < (int)points[i].size() && points[i][points_ptr].x + points[i][points_ptr].y >= diags[i][j];
                ++points_ptr) {

                int x = points[i][points_ptr].x;
                int y = points[i][points_ptr].y;

                auto it = costs.find({x, y});
                int rl_val = min(
                    it != costs.end() ? it->second : calc_cost(x, n + x - y + 2, n + x - y, costs.find({x + 1, y})),
                    it != costs.end() ? it->second : calc_cost(y, n + x - y - 2, n + x - y, costs.find({x, y + 1}))
                );

                if (lf <= n + x - y && n + x - y <= rf) {
                    new_vals.push_back({n + x - y, rl_val});
                }
            }

            for (int i = 0; i < (int)new_vals.size(); ++i) {
                cur_add = (cur_add - dp[new_vals[i].first]) % MOD;
                cur_add = (cur_add + new_vals[i].second) % MOD;
                dp[new_vals[i].first] = new_vals[i].second;
            }

            /*
            cerr << "Now " << diags[i][j] << endl;
            for (int i = lf; i <= rf; i += 2) {
                cerr << dp[i] << " ";
            }
            cerr << endl;
            */

            ans = (ans + cur_add) % MOD;
        }
    }

    if (ans < 0) {
        ans += MOD;
    }

    printf("%d\n", ans);

    return 0;
}

Compilation message

golf.cpp:22: warning: ignoring #pragma comment  [-Wunknown-pragmas]
   22 | #pragma comment(linker, "/STACK:256000000")
      | 
golf.cpp: In function 'int main()':
golf.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%lld%lld%d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |             scanf("%d%d%d", &x, &y, &c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 693 ms 29692 KB Output is correct
11 Correct 650 ms 29636 KB Output is correct
12 Correct 644 ms 29580 KB Output is correct
13 Correct 654 ms 29348 KB Output is correct
14 Correct 588 ms 29608 KB Output is correct
15 Correct 628 ms 29792 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 21 ms 2004 KB Output is correct
19 Correct 18 ms 1784 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 593 ms 29716 KB Output is correct
23 Correct 519 ms 29608 KB Output is correct
24 Correct 541 ms 29736 KB Output is correct
25 Correct 511 ms 29612 KB Output is correct
26 Correct 638 ms 29784 KB Output is correct
27 Correct 605 ms 29672 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 456 ms 29564 KB Output is correct
33 Correct 510 ms 29588 KB Output is correct
34 Correct 379 ms 29500 KB Output is correct
35 Correct 370 ms 29480 KB Output is correct
36 Correct 358 ms 29232 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 79 ms 6112 KB Output is correct
4 Correct 502 ms 28456 KB Output is correct
5 Correct 723 ms 50224 KB Output is correct
6 Correct 1137 ms 50060 KB Output is correct
7 Correct 1158 ms 50096 KB Output is correct
8 Correct 560 ms 41740 KB Output is correct
9 Correct 713 ms 45588 KB Output is correct
10 Correct 807 ms 48680 KB Output is correct
11 Correct 937 ms 49576 KB Output is correct
12 Correct 869 ms 50064 KB Output is correct
13 Correct 924 ms 49500 KB Output is correct
14 Correct 863 ms 49104 KB Output is correct
15 Correct 720 ms 37780 KB Output is correct
16 Correct 760 ms 37808 KB Output is correct
17 Correct 1383 ms 50068 KB Output is correct
18 Correct 700 ms 37832 KB Output is correct
19 Correct 634 ms 31536 KB Output is correct
20 Correct 689 ms 31656 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 384 KB Output is correct
24 Correct 0 ms 256 KB Output is correct
25 Correct 0 ms 256 KB Output is correct
26 Correct 364 ms 30116 KB Output is correct
27 Correct 406 ms 31016 KB Output is correct
28 Correct 328 ms 27812 KB Output is correct
29 Correct 316 ms 27572 KB Output is correct
30 Correct 316 ms 27648 KB Output is correct
31 Correct 343 ms 28204 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 20164 KB Output is correct
2 Correct 304 ms 20408 KB Output is correct
3 Correct 817 ms 31332 KB Output is correct
4 Correct 563 ms 31024 KB Output is correct
5 Correct 622 ms 31168 KB Output is correct
6 Correct 455 ms 28152 KB Output is correct
7 Correct 517 ms 31268 KB Output is correct
8 Correct 565 ms 31264 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 693 ms 29692 KB Output is correct
11 Correct 650 ms 29636 KB Output is correct
12 Correct 644 ms 29580 KB Output is correct
13 Correct 654 ms 29348 KB Output is correct
14 Correct 588 ms 29608 KB Output is correct
15 Correct 628 ms 29792 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 21 ms 2004 KB Output is correct
19 Correct 18 ms 1784 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 593 ms 29716 KB Output is correct
23 Correct 519 ms 29608 KB Output is correct
24 Correct 541 ms 29736 KB Output is correct
25 Correct 511 ms 29612 KB Output is correct
26 Correct 638 ms 29784 KB Output is correct
27 Correct 605 ms 29672 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 456 ms 29564 KB Output is correct
33 Correct 510 ms 29588 KB Output is correct
34 Correct 379 ms 29500 KB Output is correct
35 Correct 370 ms 29480 KB Output is correct
36 Correct 358 ms 29232 KB Output is correct
37 Correct 660 ms 29612 KB Output is correct
38 Correct 699 ms 29812 KB Output is correct
39 Correct 654 ms 29744 KB Output is correct
40 Correct 719 ms 29548 KB Output is correct
41 Correct 615 ms 29724 KB Output is correct
42 Correct 542 ms 29732 KB Output is correct
43 Correct 562 ms 29776 KB Output is correct
44 Correct 534 ms 29740 KB Output is correct
45 Correct 680 ms 29672 KB Output is correct
46 Correct 584 ms 29724 KB Output is correct
47 Correct 8 ms 768 KB Output is correct
48 Correct 7 ms 768 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 34468 KB Output is correct
2 Correct 856 ms 32772 KB Output is correct
3 Correct 756 ms 31664 KB Output is correct
4 Correct 738 ms 31652 KB Output is correct
5 Correct 34 ms 3568 KB Output is correct
6 Correct 101 ms 8660 KB Output is correct
7 Correct 570 ms 29864 KB Output is correct
8 Correct 547 ms 29784 KB Output is correct
9 Correct 721 ms 31024 KB Output is correct
10 Correct 660 ms 31212 KB Output is correct
11 Correct 862 ms 31216 KB Output is correct
12 Correct 719 ms 31256 KB Output is correct
13 Correct 955 ms 31404 KB Output is correct
14 Correct 823 ms 31152 KB Output is correct
15 Correct 750 ms 29740 KB Output is correct
16 Correct 566 ms 29860 KB Output is correct
17 Correct 1030 ms 29740 KB Output is correct
18 Correct 612 ms 31372 KB Output is correct
19 Correct 596 ms 29868 KB Output is correct
20 Correct 1006 ms 28216 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 492 ms 29484 KB Output is correct
23 Correct 504 ms 29612 KB Output is correct
24 Correct 603 ms 29616 KB Output is correct
25 Correct 86 ms 6244 KB Output is correct
26 Correct 139 ms 7652 KB Output is correct
27 Correct 142 ms 11616 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 34468 KB Output is correct
2 Correct 856 ms 32772 KB Output is correct
3 Correct 756 ms 31664 KB Output is correct
4 Correct 738 ms 31652 KB Output is correct
5 Correct 34 ms 3568 KB Output is correct
6 Correct 101 ms 8660 KB Output is correct
7 Correct 570 ms 29864 KB Output is correct
8 Correct 547 ms 29784 KB Output is correct
9 Correct 721 ms 31024 KB Output is correct
10 Correct 660 ms 31212 KB Output is correct
11 Correct 862 ms 31216 KB Output is correct
12 Correct 719 ms 31256 KB Output is correct
13 Correct 955 ms 31404 KB Output is correct
14 Correct 823 ms 31152 KB Output is correct
15 Correct 750 ms 29740 KB Output is correct
16 Correct 566 ms 29860 KB Output is correct
17 Correct 1030 ms 29740 KB Output is correct
18 Correct 612 ms 31372 KB Output is correct
19 Correct 596 ms 29868 KB Output is correct
20 Correct 1006 ms 28216 KB Output is correct
21 Correct 0 ms 256 KB Output is correct
22 Correct 492 ms 29484 KB Output is correct
23 Correct 504 ms 29612 KB Output is correct
24 Correct 603 ms 29616 KB Output is correct
25 Correct 86 ms 6244 KB Output is correct
26 Correct 139 ms 7652 KB Output is correct
27 Correct 142 ms 11616 KB Output is correct
28 Correct 1328 ms 71288 KB Output is correct
29 Correct 1156 ms 51240 KB Output is correct
30 Correct 1006 ms 50220 KB Output is correct
31 Correct 1263 ms 71264 KB Output is correct
32 Correct 1089 ms 71320 KB Output is correct
33 Correct 730 ms 29780 KB Output is correct
34 Correct 671 ms 29736 KB Output is correct
35 Correct 757 ms 29804 KB Output is correct
36 Correct 860 ms 34344 KB Output is correct
37 Correct 566 ms 29768 KB Output is correct
38 Correct 1743 ms 29188 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 693 ms 29692 KB Output is correct
11 Correct 650 ms 29636 KB Output is correct
12 Correct 644 ms 29580 KB Output is correct
13 Correct 654 ms 29348 KB Output is correct
14 Correct 588 ms 29608 KB Output is correct
15 Correct 628 ms 29792 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 21 ms 2004 KB Output is correct
19 Correct 18 ms 1784 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 593 ms 29716 KB Output is correct
23 Correct 519 ms 29608 KB Output is correct
24 Correct 541 ms 29736 KB Output is correct
25 Correct 511 ms 29612 KB Output is correct
26 Correct 638 ms 29784 KB Output is correct
27 Correct 605 ms 29672 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 456 ms 29564 KB Output is correct
33 Correct 510 ms 29588 KB Output is correct
34 Correct 379 ms 29500 KB Output is correct
35 Correct 370 ms 29480 KB Output is correct
36 Correct 358 ms 29232 KB Output is correct
37 Correct 312 ms 20164 KB Output is correct
38 Correct 304 ms 20408 KB Output is correct
39 Correct 817 ms 31332 KB Output is correct
40 Correct 563 ms 31024 KB Output is correct
41 Correct 622 ms 31168 KB Output is correct
42 Correct 455 ms 28152 KB Output is correct
43 Correct 517 ms 31268 KB Output is correct
44 Correct 565 ms 31264 KB Output is correct
45 Correct 1 ms 256 KB Output is correct
46 Correct 0 ms 256 KB Output is correct
47 Correct 939 ms 34468 KB Output is correct
48 Correct 856 ms 32772 KB Output is correct
49 Correct 756 ms 31664 KB Output is correct
50 Correct 738 ms 31652 KB Output is correct
51 Correct 34 ms 3568 KB Output is correct
52 Correct 101 ms 8660 KB Output is correct
53 Correct 570 ms 29864 KB Output is correct
54 Correct 547 ms 29784 KB Output is correct
55 Correct 721 ms 31024 KB Output is correct
56 Correct 660 ms 31212 KB Output is correct
57 Correct 862 ms 31216 KB Output is correct
58 Correct 719 ms 31256 KB Output is correct
59 Correct 955 ms 31404 KB Output is correct
60 Correct 823 ms 31152 KB Output is correct
61 Correct 750 ms 29740 KB Output is correct
62 Correct 566 ms 29860 KB Output is correct
63 Correct 1030 ms 29740 KB Output is correct
64 Correct 612 ms 31372 KB Output is correct
65 Correct 596 ms 29868 KB Output is correct
66 Correct 1006 ms 28216 KB Output is correct
67 Correct 0 ms 256 KB Output is correct
68 Correct 492 ms 29484 KB Output is correct
69 Correct 504 ms 29612 KB Output is correct
70 Correct 603 ms 29616 KB Output is correct
71 Correct 86 ms 6244 KB Output is correct
72 Correct 139 ms 7652 KB Output is correct
73 Correct 142 ms 11616 KB Output is correct
74 Correct 974 ms 34344 KB Output is correct
75 Correct 879 ms 32688 KB Output is correct
76 Correct 777 ms 31664 KB Output is correct
77 Correct 799 ms 31660 KB Output is correct
78 Correct 37 ms 3568 KB Output is correct
79 Correct 98 ms 8660 KB Output is correct
80 Correct 645 ms 29992 KB Output is correct
81 Correct 595 ms 29872 KB Output is correct
82 Correct 781 ms 31024 KB Output is correct
83 Correct 676 ms 31140 KB Output is correct
84 Correct 874 ms 31388 KB Output is correct
85 Correct 766 ms 31276 KB Output is correct
86 Correct 985 ms 31272 KB Output is correct
87 Correct 890 ms 31240 KB Output is correct
88 Correct 695 ms 29744 KB Output is correct
89 Correct 571 ms 29604 KB Output is correct
90 Correct 616 ms 29740 KB Output is correct
91 Correct 614 ms 31308 KB Output is correct
92 Correct 631 ms 29840 KB Output is correct
93 Correct 823 ms 27824 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1068 KB Output is correct
2 Correct 9 ms 1068 KB Output is correct
3 Correct 10 ms 1068 KB Output is correct
4 Correct 9 ms 1068 KB Output is correct
5 Correct 11 ms 1068 KB Output is correct
6 Correct 14 ms 1024 KB Output is correct
7 Correct 13 ms 1068 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 11 ms 1024 KB Output is correct
10 Correct 8 ms 896 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 7 ms 768 KB Output is correct
13 Correct 9 ms 768 KB Output is correct
14 Correct 7 ms 768 KB Output is correct
15 Correct 5 ms 896 KB Output is correct
16 Correct 14 ms 640 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 3 ms 512 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 693 ms 29692 KB Output is correct
11 Correct 650 ms 29636 KB Output is correct
12 Correct 644 ms 29580 KB Output is correct
13 Correct 654 ms 29348 KB Output is correct
14 Correct 588 ms 29608 KB Output is correct
15 Correct 628 ms 29792 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 21 ms 2004 KB Output is correct
19 Correct 18 ms 1784 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 593 ms 29716 KB Output is correct
23 Correct 519 ms 29608 KB Output is correct
24 Correct 541 ms 29736 KB Output is correct
25 Correct 511 ms 29612 KB Output is correct
26 Correct 638 ms 29784 KB Output is correct
27 Correct 605 ms 29672 KB Output is correct
28 Correct 1 ms 256 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 456 ms 29564 KB Output is correct
33 Correct 510 ms 29588 KB Output is correct
34 Correct 379 ms 29500 KB Output is correct
35 Correct 370 ms 29480 KB Output is correct
36 Correct 358 ms 29232 KB Output is correct
37 Correct 312 ms 20164 KB Output is correct
38 Correct 304 ms 20408 KB Output is correct
39 Correct 817 ms 31332 KB Output is correct
40 Correct 563 ms 31024 KB Output is correct
41 Correct 622 ms 31168 KB Output is correct
42 Correct 455 ms 28152 KB Output is correct
43 Correct 517 ms 31268 KB Output is correct
44 Correct 565 ms 31264 KB Output is correct
45 Correct 1 ms 256 KB Output is correct
46 Correct 0 ms 256 KB Output is correct
47 Correct 0 ms 256 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 79 ms 6112 KB Output is correct
50 Correct 502 ms 28456 KB Output is correct
51 Correct 723 ms 50224 KB Output is correct
52 Correct 1137 ms 50060 KB Output is correct
53 Correct 1158 ms 50096 KB Output is correct
54 Correct 560 ms 41740 KB Output is correct
55 Correct 713 ms 45588 KB Output is correct
56 Correct 807 ms 48680 KB Output is correct
57 Correct 937 ms 49576 KB Output is correct
58 Correct 869 ms 50064 KB Output is correct
59 Correct 924 ms 49500 KB Output is correct
60 Correct 863 ms 49104 KB Output is correct
61 Correct 720 ms 37780 KB Output is correct
62 Correct 760 ms 37808 KB Output is correct
63 Correct 1383 ms 50068 KB Output is correct
64 Correct 700 ms 37832 KB Output is correct
65 Correct 634 ms 31536 KB Output is correct
66 Correct 689 ms 31656 KB Output is correct
67 Correct 1 ms 384 KB Output is correct
68 Correct 1 ms 384 KB Output is correct
69 Correct 2 ms 384 KB Output is correct
70 Correct 0 ms 256 KB Output is correct
71 Correct 0 ms 256 KB Output is correct
72 Correct 364 ms 30116 KB Output is correct
73 Correct 406 ms 31016 KB Output is correct
74 Correct 328 ms 27812 KB Output is correct
75 Correct 316 ms 27572 KB Output is correct
76 Correct 316 ms 27648 KB Output is correct
77 Correct 343 ms 28204 KB Output is correct
78 Correct 660 ms 29612 KB Output is correct
79 Correct 699 ms 29812 KB Output is correct
80 Correct 654 ms 29744 KB Output is correct
81 Correct 719 ms 29548 KB Output is correct
82 Correct 615 ms 29724 KB Output is correct
83 Correct 542 ms 29732 KB Output is correct
84 Correct 562 ms 29776 KB Output is correct
85 Correct 534 ms 29740 KB Output is correct
86 Correct 680 ms 29672 KB Output is correct
87 Correct 584 ms 29724 KB Output is correct
88 Correct 8 ms 768 KB Output is correct
89 Correct 7 ms 768 KB Output is correct
90 Correct 939 ms 34468 KB Output is correct
91 Correct 856 ms 32772 KB Output is correct
92 Correct 756 ms 31664 KB Output is correct
93 Correct 738 ms 31652 KB Output is correct
94 Correct 34 ms 3568 KB Output is correct
95 Correct 101 ms 8660 KB Output is correct
96 Correct 570 ms 29864 KB Output is correct
97 Correct 547 ms 29784 KB Output is correct
98 Correct 721 ms 31024 KB Output is correct
99 Correct 660 ms 31212 KB Output is correct
100 Correct 862 ms 31216 KB Output is correct
101 Correct 719 ms 31256 KB Output is correct
102 Correct 955 ms 31404 KB Output is correct
103 Correct 823 ms 31152 KB Output is correct
104 Correct 750 ms 29740 KB Output is correct
105 Correct 566 ms 29860 KB Output is correct
106 Correct 1030 ms 29740 KB Output is correct
107 Correct 612 ms 31372 KB Output is correct
108 Correct 596 ms 29868 KB Output is correct
109 Correct 1006 ms 28216 KB Output is correct
110 Correct 0 ms 256 KB Output is correct
111 Correct 492 ms 29484 KB Output is correct
112 Correct 504 ms 29612 KB Output is correct
113 Correct 603 ms 29616 KB Output is correct
114 Correct 86 ms 6244 KB Output is correct
115 Correct 139 ms 7652 KB Output is correct
116 Correct 142 ms 11616 KB Output is correct
117 Correct 1328 ms 71288 KB Output is correct
118 Correct 1156 ms 51240 KB Output is correct
119 Correct 1006 ms 50220 KB Output is correct
120 Correct 1263 ms 71264 KB Output is correct
121 Correct 1089 ms 71320 KB Output is correct
122 Correct 730 ms 29780 KB Output is correct
123 Correct 671 ms 29736 KB Output is correct
124 Correct 757 ms 29804 KB Output is correct
125 Correct 860 ms 34344 KB Output is correct
126 Correct 566 ms 29768 KB Output is correct
127 Correct 1743 ms 29188 KB Output is correct
128 Correct 974 ms 34344 KB Output is correct
129 Correct 879 ms 32688 KB Output is correct
130 Correct 777 ms 31664 KB Output is correct
131 Correct 799 ms 31660 KB Output is correct
132 Correct 37 ms 3568 KB Output is correct
133 Correct 98 ms 8660 KB Output is correct
134 Correct 645 ms 29992 KB Output is correct
135 Correct 595 ms 29872 KB Output is correct
136 Correct 781 ms 31024 KB Output is correct
137 Correct 676 ms 31140 KB Output is correct
138 Correct 874 ms 31388 KB Output is correct
139 Correct 766 ms 31276 KB Output is correct
140 Correct 985 ms 31272 KB Output is correct
141 Correct 890 ms 31240 KB Output is correct
142 Correct 695 ms 29744 KB Output is correct
143 Correct 571 ms 29604 KB Output is correct
144 Correct 616 ms 29740 KB Output is correct
145 Correct 614 ms 31308 KB Output is correct
146 Correct 631 ms 29840 KB Output is correct
147 Correct 823 ms 27824 KB Output is correct
148 Correct 12 ms 1068 KB Output is correct
149 Correct 9 ms 1068 KB Output is correct
150 Correct 10 ms 1068 KB Output is correct
151 Correct 9 ms 1068 KB Output is correct
152 Correct 11 ms 1068 KB Output is correct
153 Correct 14 ms 1024 KB Output is correct
154 Correct 13 ms 1068 KB Output is correct
155 Correct 8 ms 1024 KB Output is correct
156 Correct 11 ms 1024 KB Output is correct
157 Correct 8 ms 896 KB Output is correct
158 Correct 8 ms 768 KB Output is correct
159 Correct 7 ms 768 KB Output is correct
160 Correct 9 ms 768 KB Output is correct
161 Correct 7 ms 768 KB Output is correct
162 Correct 5 ms 896 KB Output is correct
163 Correct 14 ms 640 KB Output is correct
164 Correct 1 ms 256 KB Output is correct
165 Correct 1 ms 256 KB Output is correct
166 Correct 3 ms 640 KB Output is correct
167 Correct 4 ms 640 KB Output is correct
168 Correct 5 ms 768 KB Output is correct
169 Correct 3 ms 512 KB Output is correct
170 Correct 3 ms 512 KB Output is correct
171 Correct 3 ms 512 KB Output is correct
172 Correct 1244 ms 71332 KB Output is correct
173 Correct 1128 ms 51220 KB Output is correct
174 Correct 1036 ms 50224 KB Output is correct
175 Correct 1042 ms 50228 KB Output is correct
176 Correct 1018 ms 71372 KB Output is correct
177 Correct 1384 ms 71200 KB Output is correct
178 Correct 823 ms 29724 KB Output is correct
179 Correct 610 ms 29864 KB Output is correct
180 Correct 1168 ms 29744 KB Output is correct
181 Correct 934 ms 34504 KB Output is correct
182 Correct 633 ms 29744 KB Output is correct
183 Correct 1605 ms 30128 KB Output is correct