oj.uz

Submission #697177

# Submission time Handle Problem Language Result Execution time Memory
697177 2023-02-08T17:30:30 Z whqkrtk04 Painting Walls (APIO20_paint) C++17
40 / 100
 1500 ms 88396 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const deque<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

vector<int> evaluate(int M, deque<int> &chk, vector<int> &can) {
    vector<int> ret;
    if(chk.size() > can.size() || chk.empty()) return ret;
    for(int i = 0; i < can.size(); i++) {
        int diff = ((can[i]-chk[0])%M+M)%M;
        bool valid = true;
        for(int j = 0; j < chk.size(); j++) {
            int tmp = ((chk[j]+diff)%M+M)%M;
            auto iter = lower_bound(can.begin(), can.end(), tmp);
            if(iter == can.end() || *iter != tmp) valid = false;
        }
        if(valid) ret.push_back(diff);
    }
    return ret;
}

template <typename node_seg, typename node_query = node_seg, typename index_t = int>
class Segtree {
	private:
	const size_t n;
	std::vector<node_seg> seg;

	void init(const size_t i, const index_t s, const index_t e, const std::vector<node_seg> &A) {
		if(s+1 == e) seg[i] = A[s];
		else {
			init(i<<1, s, s+e>>1, A);
			init(i<<1|1, s+e>>1, e, A);
			seg[i] = seg[i<<1]+seg[i<<1|1];
		}
	}

	void update(const size_t i, const index_t s, const index_t e, const index_t j, const node_query &x) {
		if(j >= e || s > j) return;
		if(s+1 == e) seg[i] += x;
		else {
			update(i<<1, s, s+e>>1, j, x);
			update(i<<1|1, s+e>>1, e, j, x);
			seg[i] = seg[i<<1]+seg[i<<1|1];
		}
	}

	node_seg query(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r) const {
		if(e <= l || r <= s) return node_seg::inf();
		if(l <= s && e <= r) return seg[i];
		return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
	}

	public:
	Segtree(const int n) : n(n) {
		seg.resize(4*n, node_seg::inf());
	}
	Segtree(const std::vector<node_seg> &A) : n(A.size()) {
		seg.resize(4*n, node_seg::inf());
		init(1, 0, n, A);
	}
	void update(const index_t j, const node_query &x) { update(1, 0, n, j, x); }
	node_seg query(const index_t l, const index_t r) const { return query(1, 0, n, l, r); }
};

struct min_node {
    int x;
    static min_node inf() { return {INF}; }
    min_node operator+(const min_node &y) { return {min(x, y.x)}; }
    void operator+=(const min_node &y) { x = min(x, y.x); }
};

vector<bool> solve(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<deque<int>> chk(K);
    vector<vector<int>> verdict(K), can(K);
    vector<int> cnt(M, 0);
    vector<bool> can_paint(N, false);
    int macnt = 0, uniqcnt = 0;
    for(int i = 0; i < M; i++) for(auto j : B[i]) can[j].push_back(i);
    for(int i = 0; i < M; i++) {
        for(auto j : verdict[C[i]]) if(cnt[j]-- == uniqcnt) macnt--;
        if(chk[C[i]].empty()) uniqcnt++, macnt = 0;
        chk[C[i]].push_back(i);
        verdict[C[i]] = evaluate(M, chk[C[i]], can[C[i]]);
        for(auto j : verdict[C[i]]) if(++cnt[j] == uniqcnt) macnt++;
        //cout << "print : " << i << " " << macnt << " " << uniqcnt << "\n" << cnt << " " << verdict << endl;
    }    
    can_paint[M-1] = macnt > 0;
    for(int i = M; i < N; i++) {
        if(C[i] != C[i-M]) {
            for(auto j : verdict[C[i]]) if(cnt[j]-- == uniqcnt) macnt--;
            for(auto j : verdict[C[i-M]]) if(cnt[j]-- == uniqcnt) macnt--;

            if(chk[C[i]].empty()) uniqcnt++, macnt = 0;
            chk[C[i]].push_back(i);
            verdict[C[i]] = evaluate(M, chk[C[i]], can[C[i]]);

            chk[C[i-M]].pop_front();
            if(chk[C[i-M]].empty()) uniqcnt--;
            verdict[C[i-M]] = evaluate(M, chk[C[i-M]], can[C[i-M]]);

            for(auto j : verdict[C[i]]) if(++cnt[j] == uniqcnt) macnt++;
            for(auto j : verdict[C[i-M]]) if(++cnt[j] == uniqcnt) macnt++;
        }
        can_paint[i] = macnt > 0;
        //cout << "print : " << i << " " << macnt << " " << uniqcnt << "\n" << cnt << " " << verdict << endl;
    }
    return can_paint;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<bool> can_paint = solve(N, M, K, C, A, B);
    //cout << can_paint;
    Segtree<min_node> dp(vector<min_node>(N, min_node::inf()));
    if(can_paint[M-1]) dp.update(M-1, {1});
    for(int i = M; i < N; i++) {
        if(can_paint[i]) {
            int tmp = dp.query(i-M, i).x;
            dp.update(i, {++tmp});
        }
    }
    int ans = dp.query(N-1, N).x;
    if(ans == INF) return -1;
    else return ans;
}

Compilation message

paint.cpp: In function 'std::vector<int> evaluate(int, std::deque<int>&, std::vector<int>&)':
paint.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < can.size(); i++) {
      |                    ~~^~~~~~~~~~~~
paint.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int j = 0; j < chk.size(); j++) {
      |                        ~~^~~~~~~~~~~~
paint.cpp: In instantiation of 'void Segtree<node_seg, node_query, index_t>::init(size_t, index_t, index_t, const std::vector<_Tp>&) [with node_seg = min_node; node_query = min_node; index_t = int; size_t = long unsigned int]':
paint.cpp:74:3:   required from 'Segtree<node_seg, node_query, index_t>::Segtree(const std::vector<_Tp>&) [with node_seg = min_node; node_query = min_node; index_t = int]'
paint.cpp:128:62:   required from here
paint.cpp:46:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |    init(i<<1, s, s+e>>1, A);
      |                  ~^~
paint.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |    init(i<<1|1, s+e>>1, e, A);
      |                 ~^~
paint.cpp: In instantiation of 'void Segtree<node_seg, node_query, index_t>::update(size_t, index_t, index_t, index_t, const node_query&) [with node_seg = min_node; node_query = min_node; index_t = int; size_t = long unsigned int]':
paint.cpp:76:60:   required from 'void Segtree<node_seg, node_query, index_t>::update(index_t, const node_query&) [with node_seg = min_node; node_query = min_node; index_t = int]'
paint.cpp:129:42:   required from here
paint.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |    update(i<<1, s, s+e>>1, j, x);
      |                    ~^~
paint.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |    update(i<<1|1, s+e>>1, e, j, x);
      |                   ~^~
paint.cpp: In instantiation of 'node_seg Segtree<node_seg, node_query, index_t>::query(size_t, index_t, index_t, index_t, index_t) const [with node_seg = min_node; node_query = min_node; index_t = int; size_t = long unsigned int]':
paint.cpp:77:71:   required from 'node_seg Segtree<node_seg, node_query, index_t>::query(index_t, index_t) const [with node_seg = min_node; node_query = min_node; index_t = int]'
paint.cpp:132:38:   required from here
paint.cpp:65:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                         ~^~
paint.cpp:65:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                                                     ~^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 42 ms 72264 KB Output is correct
14 Correct 43 ms 72296 KB Output is correct
15 Correct 41 ms 72364 KB Output is correct
16 Correct 47 ms 72348 KB Output is correct
17 Correct 46 ms 72288 KB Output is correct
18 Correct 45 ms 72376 KB Output is correct
19 Correct 45 ms 72268 KB Output is correct
20 Correct 43 ms 72272 KB Output is correct
21 Correct 41 ms 72284 KB Output is correct
22 Correct 61 ms 77160 KB Output is correct
23 Correct 64 ms 77148 KB Output is correct
24 Correct 60 ms 77124 KB Output is correct
25 Correct 5 ms 852 KB Output is correct
26 Correct 5 ms 852 KB Output is correct
27 Correct 5 ms 852 KB Output is correct
28 Correct 4 ms 852 KB Output is correct
29 Correct 4 ms 796 KB Output is correct
30 Correct 4 ms 852 KB Output is correct
31 Correct 58 ms 73812 KB Output is correct
32 Correct 58 ms 73904 KB Output is correct
33 Correct 59 ms 73804 KB Output is correct
34 Correct 58 ms 73900 KB Output is correct
35 Correct 58 ms 73820 KB Output is correct
36 Correct 57 ms 73912 KB Output is correct
37 Correct 73 ms 77848 KB Output is correct
38 Correct 69 ms 77772 KB Output is correct
39 Correct 76 ms 77772 KB Output is correct
40 Correct 22 ms 2928 KB Output is correct
41 Correct 14 ms 1880 KB Output is correct
42 Correct 21 ms 3216 KB Output is correct
43 Correct 11 ms 2212 KB Output is correct
44 Correct 10 ms 2024 KB Output is correct
45 Correct 16 ms 3220 KB Output is correct
46 Correct 129 ms 86320 KB Output is correct
47 Correct 92 ms 73208 KB Output is correct
48 Correct 90 ms 72116 KB Output is correct
49 Correct 97 ms 72776 KB Output is correct
50 Correct 102 ms 74216 KB Output is correct
51 Correct 105 ms 59384 KB Output is correct
52 Correct 36 ms 3268 KB Output is correct
53 Correct 24 ms 3148 KB Output is correct
54 Correct 21 ms 3148 KB Output is correct
55 Correct 17 ms 3148 KB Output is correct
56 Correct 16 ms 3188 KB Output is correct
57 Correct 16 ms 3148 KB Output is correct
58 Correct 137 ms 87900 KB Output is correct
59 Correct 138 ms 88396 KB Output is correct
60 Correct 138 ms 88360 KB Output is correct
61 Correct 138 ms 88348 KB Output is correct
62 Correct 143 ms 88384 KB Output is correct
63 Correct 141 ms 88396 KB Output is correct
64 Correct 125 ms 86572 KB Output is correct
65 Correct 130 ms 86560 KB Output is correct
66 Correct 127 ms 86564 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 42 ms 72264 KB Output is correct
14 Correct 43 ms 72296 KB Output is correct
15 Correct 41 ms 72364 KB Output is correct
16 Correct 47 ms 72348 KB Output is correct
17 Correct 46 ms 72288 KB Output is correct
18 Correct 45 ms 72376 KB Output is correct
19 Correct 45 ms 72268 KB Output is correct
20 Correct 43 ms 72272 KB Output is correct
21 Correct 41 ms 72284 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 304 KB Output is correct
25 Correct 0 ms 300 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 296 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 2 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 2 ms 212 KB Output is correct
33 Correct 36 ms 61900 KB Output is correct
34 Correct 27 ms 46292 KB Output is correct
35 Correct 24 ms 40536 KB Output is correct
36 Correct 42 ms 70832 KB Output is correct
37 Correct 33 ms 57412 KB Output is correct
38 Correct 37 ms 63404 KB Output is correct
39 Correct 1 ms 428 KB Output is correct
40 Correct 31 ms 54588 KB Output is correct
41 Correct 1 ms 468 KB Output is correct
42 Correct 40 ms 68364 KB Output is correct
43 Correct 38 ms 66516 KB Output is correct
44 Correct 1 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 3 ms 300 KB Output is correct
47 Correct 3 ms 304 KB Output is correct
48 Correct 3 ms 296 KB Output is correct
49 Correct 3 ms 340 KB Output is correct
50 Correct 43 ms 72288 KB Output is correct
51 Correct 43 ms 72268 KB Output is correct
52 Correct 45 ms 72380 KB Output is correct
53 Correct 43 ms 72268 KB Output is correct
54 Correct 44 ms 72268 KB Output is correct
55 Correct 44 ms 72300 KB Output is correct
56 Correct 42 ms 72284 KB Output is correct
57 Correct 1 ms 688 KB Output is correct
58 Correct 45 ms 72264 KB Output is correct
59 Correct 1 ms 596 KB Output is correct
60 Correct 45 ms 72372 KB Output is correct
61 Correct 1 ms 684 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 42 ms 72264 KB Output is correct
16 Correct 43 ms 72296 KB Output is correct
17 Correct 41 ms 72364 KB Output is correct
18 Correct 47 ms 72348 KB Output is correct
19 Correct 46 ms 72288 KB Output is correct
20 Correct 45 ms 72376 KB Output is correct
21 Correct 45 ms 72268 KB Output is correct
22 Correct 43 ms 72272 KB Output is correct
23 Correct 41 ms 72284 KB Output is correct
24 Correct 61 ms 77160 KB Output is correct
25 Correct 64 ms 77148 KB Output is correct
26 Correct 60 ms 77124 KB Output is correct
27 Correct 0 ms 304 KB Output is correct
28 Correct 0 ms 300 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 296 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 2 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 2 ms 212 KB Output is correct
36 Correct 36 ms 61900 KB Output is correct
37 Correct 27 ms 46292 KB Output is correct
38 Correct 24 ms 40536 KB Output is correct
39 Correct 42 ms 70832 KB Output is correct
40 Correct 33 ms 57412 KB Output is correct
41 Correct 37 ms 63404 KB Output is correct
42 Correct 1 ms 428 KB Output is correct
43 Correct 31 ms 54588 KB Output is correct
44 Correct 1 ms 468 KB Output is correct
45 Correct 40 ms 68364 KB Output is correct
46 Correct 38 ms 66516 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 3 ms 300 KB Output is correct
50 Correct 3 ms 304 KB Output is correct
51 Correct 3 ms 296 KB Output is correct
52 Correct 3 ms 340 KB Output is correct
53 Correct 43 ms 72288 KB Output is correct
54 Correct 43 ms 72268 KB Output is correct
55 Correct 45 ms 72380 KB Output is correct
56 Correct 43 ms 72268 KB Output is correct
57 Correct 44 ms 72268 KB Output is correct
58 Correct 44 ms 72300 KB Output is correct
59 Correct 42 ms 72284 KB Output is correct
60 Correct 1 ms 688 KB Output is correct
61 Correct 45 ms 72264 KB Output is correct
62 Correct 1 ms 596 KB Output is correct
63 Correct 45 ms 72372 KB Output is correct
64 Correct 1 ms 684 KB Output is correct
65 Correct 37 ms 296 KB Output is correct
66 Correct 9 ms 300 KB Output is correct
67 Correct 81 ms 316 KB Output is correct
68 Correct 25 ms 212 KB Output is correct
69 Correct 51 ms 300 KB Output is correct
70 Correct 36 ms 61644 KB Output is correct
71 Correct 34 ms 50752 KB Output is correct
72 Correct 27 ms 44020 KB Output is correct
73 Correct 33 ms 50984 KB Output is correct
74 Correct 41 ms 57844 KB Output is correct
75 Correct 44 ms 71208 KB Output is correct
76 Correct 47 ms 54220 KB Output is correct
77 Correct 50 ms 66764 KB Output is correct
78 Correct 69 ms 74508 KB Output is correct
79 Correct 47 ms 344 KB Output is correct
80 Correct 193 ms 340 KB Output is correct
81 Correct 192 ms 340 KB Output is correct
82 Correct 173 ms 300 KB Output is correct
83 Correct 154 ms 340 KB Output is correct
84 Correct 57 ms 72684 KB Output is correct
85 Correct 49 ms 72680 KB Output is correct
86 Correct 44 ms 72740 KB Output is correct
87 Correct 50 ms 72648 KB Output is correct
88 Correct 48 ms 72636 KB Output is correct
89 Correct 44 ms 72704 KB Output is correct
90 Correct 70 ms 77560 KB Output is correct
91 Correct 88 ms 77512 KB Output is correct
92 Correct 69 ms 77516 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 42 ms 72264 KB Output is correct
16 Correct 43 ms 72296 KB Output is correct
17 Correct 41 ms 72364 KB Output is correct
18 Correct 47 ms 72348 KB Output is correct
19 Correct 46 ms 72288 KB Output is correct
20 Correct 45 ms 72376 KB Output is correct
21 Correct 45 ms 72268 KB Output is correct
22 Correct 43 ms 72272 KB Output is correct
23 Correct 41 ms 72284 KB Output is correct
24 Correct 61 ms 77160 KB Output is correct
25 Correct 64 ms 77148 KB Output is correct
26 Correct 60 ms 77124 KB Output is correct
27 Correct 5 ms 852 KB Output is correct
28 Correct 5 ms 852 KB Output is correct
29 Correct 5 ms 852 KB Output is correct
30 Correct 4 ms 852 KB Output is correct
31 Correct 4 ms 796 KB Output is correct
32 Correct 4 ms 852 KB Output is correct
33 Correct 58 ms 73812 KB Output is correct
34 Correct 58 ms 73904 KB Output is correct
35 Correct 59 ms 73804 KB Output is correct
36 Correct 58 ms 73900 KB Output is correct
37 Correct 58 ms 73820 KB Output is correct
38 Correct 57 ms 73912 KB Output is correct
39 Correct 73 ms 77848 KB Output is correct
40 Correct 69 ms 77772 KB Output is correct
41 Correct 76 ms 77772 KB Output is correct
42 Correct 0 ms 304 KB Output is correct
43 Correct 0 ms 300 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 296 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 2 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 2 ms 212 KB Output is correct
51 Correct 36 ms 61900 KB Output is correct
52 Correct 27 ms 46292 KB Output is correct
53 Correct 24 ms 40536 KB Output is correct
54 Correct 42 ms 70832 KB Output is correct
55 Correct 33 ms 57412 KB Output is correct
56 Correct 37 ms 63404 KB Output is correct
57 Correct 1 ms 428 KB Output is correct
58 Correct 31 ms 54588 KB Output is correct
59 Correct 1 ms 468 KB Output is correct
60 Correct 40 ms 68364 KB Output is correct
61 Correct 38 ms 66516 KB Output is correct
62 Correct 1 ms 212 KB Output is correct
63 Correct 1 ms 212 KB Output is correct
64 Correct 3 ms 300 KB Output is correct
65 Correct 3 ms 304 KB Output is correct
66 Correct 3 ms 296 KB Output is correct
67 Correct 3 ms 340 KB Output is correct
68 Correct 43 ms 72288 KB Output is correct
69 Correct 43 ms 72268 KB Output is correct
70 Correct 45 ms 72380 KB Output is correct
71 Correct 43 ms 72268 KB Output is correct
72 Correct 44 ms 72268 KB Output is correct
73 Correct 44 ms 72300 KB Output is correct
74 Correct 42 ms 72284 KB Output is correct
75 Correct 1 ms 688 KB Output is correct
76 Correct 45 ms 72264 KB Output is correct
77 Correct 1 ms 596 KB Output is correct
78 Correct 45 ms 72372 KB Output is correct
79 Correct 1 ms 684 KB Output is correct
80 Correct 37 ms 296 KB Output is correct
81 Correct 9 ms 300 KB Output is correct
82 Correct 81 ms 316 KB Output is correct
83 Correct 25 ms 212 KB Output is correct
84 Correct 51 ms 300 KB Output is correct
85 Correct 36 ms 61644 KB Output is correct
86 Correct 34 ms 50752 KB Output is correct
87 Correct 27 ms 44020 KB Output is correct
88 Correct 33 ms 50984 KB Output is correct
89 Correct 41 ms 57844 KB Output is correct
90 Correct 44 ms 71208 KB Output is correct
91 Correct 47 ms 54220 KB Output is correct
92 Correct 50 ms 66764 KB Output is correct
93 Correct 69 ms 74508 KB Output is correct
94 Correct 47 ms 344 KB Output is correct
95 Correct 193 ms 340 KB Output is correct
96 Correct 192 ms 340 KB Output is correct
97 Correct 173 ms 300 KB Output is correct
98 Correct 154 ms 340 KB Output is correct
99 Correct 57 ms 72684 KB Output is correct
100 Correct 49 ms 72680 KB Output is correct
101 Correct 44 ms 72740 KB Output is correct
102 Correct 50 ms 72648 KB Output is correct
103 Correct 48 ms 72636 KB Output is correct
104 Correct 44 ms 72704 KB Output is correct
105 Correct 70 ms 77560 KB Output is correct
106 Correct 88 ms 77512 KB Output is correct
107 Correct 69 ms 77516 KB Output is correct
108 Correct 5 ms 852 KB Output is correct
109 Execution timed out 1569 ms 608 KB Time limit exceeded
110 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 42 ms 72264 KB Output is correct
16 Correct 43 ms 72296 KB Output is correct
17 Correct 41 ms 72364 KB Output is correct
18 Correct 47 ms 72348 KB Output is correct
19 Correct 46 ms 72288 KB Output is correct
20 Correct 45 ms 72376 KB Output is correct
21 Correct 45 ms 72268 KB Output is correct
22 Correct 43 ms 72272 KB Output is correct
23 Correct 41 ms 72284 KB Output is correct
24 Correct 61 ms 77160 KB Output is correct
25 Correct 64 ms 77148 KB Output is correct
26 Correct 60 ms 77124 KB Output is correct
27 Correct 5 ms 852 KB Output is correct
28 Correct 5 ms 852 KB Output is correct
29 Correct 5 ms 852 KB Output is correct
30 Correct 4 ms 852 KB Output is correct
31 Correct 4 ms 796 KB Output is correct
32 Correct 4 ms 852 KB Output is correct
33 Correct 58 ms 73812 KB Output is correct
34 Correct 58 ms 73904 KB Output is correct
35 Correct 59 ms 73804 KB Output is correct
36 Correct 58 ms 73900 KB Output is correct
37 Correct 58 ms 73820 KB Output is correct
38 Correct 57 ms 73912 KB Output is correct
39 Correct 73 ms 77848 KB Output is correct
40 Correct 69 ms 77772 KB Output is correct
41 Correct 76 ms 77772 KB Output is correct
42 Correct 22 ms 2928 KB Output is correct
43 Correct 14 ms 1880 KB Output is correct
44 Correct 21 ms 3216 KB Output is correct
45 Correct 11 ms 2212 KB Output is correct
46 Correct 10 ms 2024 KB Output is correct
47 Correct 16 ms 3220 KB Output is correct
48 Correct 129 ms 86320 KB Output is correct
49 Correct 92 ms 73208 KB Output is correct
50 Correct 90 ms 72116 KB Output is correct
51 Correct 97 ms 72776 KB Output is correct
52 Correct 102 ms 74216 KB Output is correct
53 Correct 105 ms 59384 KB Output is correct
54 Correct 36 ms 3268 KB Output is correct
55 Correct 24 ms 3148 KB Output is correct
56 Correct 21 ms 3148 KB Output is correct
57 Correct 17 ms 3148 KB Output is correct
58 Correct 16 ms 3188 KB Output is correct
59 Correct 16 ms 3148 KB Output is correct
60 Correct 137 ms 87900 KB Output is correct
61 Correct 138 ms 88396 KB Output is correct
62 Correct 138 ms 88360 KB Output is correct
63 Correct 138 ms 88348 KB Output is correct
64 Correct 143 ms 88384 KB Output is correct
65 Correct 141 ms 88396 KB Output is correct
66 Correct 125 ms 86572 KB Output is correct
67 Correct 130 ms 86560 KB Output is correct
68 Correct 127 ms 86564 KB Output is correct
69 Correct 0 ms 304 KB Output is correct
70 Correct 0 ms 300 KB Output is correct
71 Correct 0 ms 212 KB Output is correct
72 Correct 1 ms 212 KB Output is correct
73 Correct 1 ms 296 KB Output is correct
74 Correct 1 ms 212 KB Output is correct
75 Correct 2 ms 212 KB Output is correct
76 Correct 1 ms 212 KB Output is correct
77 Correct 2 ms 212 KB Output is correct
78 Correct 36 ms 61900 KB Output is correct
79 Correct 27 ms 46292 KB Output is correct
80 Correct 24 ms 40536 KB Output is correct
81 Correct 42 ms 70832 KB Output is correct
82 Correct 33 ms 57412 KB Output is correct
83 Correct 37 ms 63404 KB Output is correct
84 Correct 1 ms 428 KB Output is correct
85 Correct 31 ms 54588 KB Output is correct
86 Correct 1 ms 468 KB Output is correct
87 Correct 40 ms 68364 KB Output is correct
88 Correct 38 ms 66516 KB Output is correct
89 Correct 1 ms 212 KB Output is correct
90 Correct 1 ms 212 KB Output is correct
91 Correct 3 ms 300 KB Output is correct
92 Correct 3 ms 304 KB Output is correct
93 Correct 3 ms 296 KB Output is correct
94 Correct 3 ms 340 KB Output is correct
95 Correct 43 ms 72288 KB Output is correct
96 Correct 43 ms 72268 KB Output is correct
97 Correct 45 ms 72380 KB Output is correct
98 Correct 43 ms 72268 KB Output is correct
99 Correct 44 ms 72268 KB Output is correct
100 Correct 44 ms 72300 KB Output is correct
101 Correct 42 ms 72284 KB Output is correct
102 Correct 1 ms 688 KB Output is correct
103 Correct 45 ms 72264 KB Output is correct
104 Correct 1 ms 596 KB Output is correct
105 Correct 45 ms 72372 KB Output is correct
106 Correct 1 ms 684 KB Output is correct
107 Correct 37 ms 296 KB Output is correct
108 Correct 9 ms 300 KB Output is correct
109 Correct 81 ms 316 KB Output is correct
110 Correct 25 ms 212 KB Output is correct
111 Correct 51 ms 300 KB Output is correct
112 Correct 36 ms 61644 KB Output is correct
113 Correct 34 ms 50752 KB Output is correct
114 Correct 27 ms 44020 KB Output is correct
115 Correct 33 ms 50984 KB Output is correct
116 Correct 41 ms 57844 KB Output is correct
117 Correct 44 ms 71208 KB Output is correct
118 Correct 47 ms 54220 KB Output is correct
119 Correct 50 ms 66764 KB Output is correct
120 Correct 69 ms 74508 KB Output is correct
121 Correct 47 ms 344 KB Output is correct
122 Correct 193 ms 340 KB Output is correct
123 Correct 192 ms 340 KB Output is correct
124 Correct 173 ms 300 KB Output is correct
125 Correct 154 ms 340 KB Output is correct
126 Correct 57 ms 72684 KB Output is correct
127 Correct 49 ms 72680 KB Output is correct
128 Correct 44 ms 72740 KB Output is correct
129 Correct 50 ms 72648 KB Output is correct
130 Correct 48 ms 72636 KB Output is correct
131 Correct 44 ms 72704 KB Output is correct
132 Correct 70 ms 77560 KB Output is correct
133 Correct 88 ms 77512 KB Output is correct
134 Correct 69 ms 77516 KB Output is correct
135 Correct 5 ms 852 KB Output is correct
136 Execution timed out 1569 ms 608 KB Time limit exceeded
137 Halted 0 ms 0 KB -