codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1383.md (15568B)


      1 Source: https://codeforces.com/blog/entry/80562
      2 
      3 We (the setters) hope you liked the problems. Here is the editorial:
      4 
      5 Tutorial is loading...
      6 
      7 **C++ solution**
      8 
      9 ```
     10 #include <iostream>
     11 
     12 #define endl '\n'
     13 
     14 using namespace std;
     15 
     16 void solve()
     17 {
     18     int n;
     19     cin >> n;
     20 
     21     string s(200, 'a');
     22     cout << s << endl;
     23 
     24     for (int i = 0; i < n; ++i)
     25     {
     26         int u;
     27         cin >> u;
     28         s[u] = s[u] == 'a' ? 'b' : 'a';
     29         cout << s << endl;
     30     }
     31 }
     32 
     33 int main()
     34 {
     35     int t;
     36     cin >> t;
     37 
     38     for (int i = 0; i < t; ++i)
     39     {
     40         solve();
     41     }
     42 
     43     return 0;
     44 }
     45 ```
     46 
     47 **Python solution**
     48 
     49 ```
     50 import sys
     51 input = sys.stdin.readline
     52 
     53 def main():
     54     t = int(input())
     55     
     56     for _ in range(t):
     57         n = int(input())
     58         a = list(map(int, input().split()))
     59     
     60         mx = max(a)
     61         ans = [ 'a' * (mx + 1) ] * (n + 1)
     62     
     63         for i, x in enumerate(a):
     64             who = 'a' if ans[i][x] == 'b' else 'b'
     65             ans[i + 1] = ans[i][:x] + who + ans[i][x + 1:]
     66     
     67         print('\n'.join(ans))    
     68 
     69 main()
     70 ```
     71 
     72 Problem idea: [dcordb](/profile/dcordb "Expert dcordb")
     73 
     74 Solution idea: [dcordb](/profile/dcordb "Expert dcordb") and [Devil](/profile/Devil "Master Devil")
     75 
     76 Tutorial is loading...
     77 
     78 **C++ solution**
     79 
     80 ```
     81 #include <bits/stdc++.h>
     82 
     83 using namespace std;
     84 
     85 int main()
     86 {
     87 	ios_base::sync_with_stdio(0), cin.tie(0);
     88 
     89 	int test;
     90 	cin >> test;
     91 	while (test--)
     92 	{
     93 		int n, k, l;
     94 		cin >> n >> k >> l;
     95 		vector<int> d(n+2, -k);
     96 		for (int i = 1; i <= n; ++i)
     97 			cin >> d[i];
     98 
     99 		set<tuple<int, int, bool>> mark;
    100 		function<bool(int, int, bool)> go = [&](int pos, int tide, bool down)
    101 		{
    102 			if (pos > n) return true;
    103 			
    104 			if (mark.find({ pos, tide, down }) != mark.end())
    105 				return false;
    106 
    107 			mark.insert({ pos, tide, down });
    108 
    109 			tide += down ? -1 : +1;
    110 			if (tide == 0) down = false;
    111 			if (tide == k) down = true;
    112 
    113 			if (d[pos] + tide <= l && go(pos, tide, down))
    114 				return true;
    115 			if (d[pos + 1] + tide <= l && go(pos + 1, tide, down))
    116 				return true;
    117 			return false;
    118 		};
    119 
    120 		if (go(0, 0, false)) cout << "Yes\n";
    121 		else cout << "No\n";
    122 	}
    123 
    124 	return 0;
    125 }
    126 ```
    127 
    128 Problem idea: [Devil](/profile/Devil "Master Devil")
    129 
    130 Solution idea: [Devil](/profile/Devil "Master Devil")
    131 
    132 Tutorial is loading...
    133 
    134 **C++ solution**
    135 
    136 ```
    137 #include <bits/stdc++.h>
    138 
    139 using namespace std;
    140 
    141 int main()
    142 {
    143 	ios_base::sync_with_stdio(0), cin.tie(0);
    144 
    145 	int test;
    146 	cin >> test;
    147 	while (test--)
    148 	{
    149 		int n, k, l;
    150 		cin >> n >> k >> l;
    151 		vector<int> d(n+1), safe = { 0 };
    152 		for (int i = 1; i <= n; ++i)
    153 		{
    154 			cin >> d[i];
    155 			if (d[i] + k <= l)
    156 				safe.push_back(i);
    157 		}
    158 
    159 		safe.push_back(n+1);
    160 		bool ok = true;
    161 		for (size_t i = 1; i < safe.size() && ok; ++i)
    162 		{
    163 			int tide = k; bool down = true;
    164 			for (int j = safe[i-1] + 1; j < safe[i]; ++j)
    165 			{
    166 				tide += down ? -1 : +1;
    167 
    168 				if (down) tide -= max(0, d[j] + tide - l);
    169 				if (tide < 0 || d[j] + tide > l) { ok = false; break; }
    170 
    171 				if (tide == 0) down = false;
    172 			}
    173 		}
    174 
    175 		if (ok) cout << "Yes\n";
    176 		else cout << "No\n";
    177 	}
    178 
    179 	return 0;
    180 }
    181 ```
    182 
    183 Problem idea: [Devil](/profile/Devil "Master Devil")
    184 
    185 Solution idea: [Devil](/profile/Devil "Master Devil")
    186 
    187 Tutorial is loading...
    188 
    189 **C++ solution**
    190 
    191 ```
    192 #include <bits/stdc++.h>
    193 
    194 using namespace std;
    195 
    196 const int Alp = 20;
    197 
    198 int main()
    199 {
    200 	ios_base::sync_with_stdio(0), cin.tie(0);
    201 
    202 	int test;
    203 	cin >> test;
    204 	while (test--)
    205 	{
    206 	    int n;
    207 		string a, b;
    208 		cin >> n >> a >> b;
    209 
    210 		bool bad = false;
    211 		vector<vector<int>> adj(Alp);
    212 		for (int i = 0; i < n; ++i)
    213 			if (a[i] != b[i])
    214 			{
    215 				if (a[i] > b[i])
    216 				{
    217 					bad = true;
    218 					cout << "-1\n";
    219 					break;
    220 				}
    221 
    222 				adj[a[i]-'a'].push_back(b[i]-'a');
    223 				adj[b[i]-'a'].push_back(a[i]-'a');
    224 			}
    225 
    226 		if (bad) continue;
    227 
    228 		vector<bool> mark(Alp);
    229 		function<void(int)> dfs = [&](int u)
    230 		{
    231 			mark[u] = true;
    232 			for (auto v : adj[u])
    233 				if (!mark[v])
    234 					dfs(v);
    235 		};
    236 
    237 		int ans = Alp;
    238 		for (int i = 0; i < Alp; ++i)
    239 			if (!mark[i])
    240 				dfs(i), --ans;
    241 		cout << ans << "\n";
    242 	}
    243 
    244 	return 0;
    245 }
    246 ```
    247 
    248 Problem idea: [Devil](/profile/Devil "Master Devil")
    249 
    250 Solution idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") and [Devil](/profile/Devil "Master Devil")
    251 
    252 Tutorial is loading...
    253 
    254 **C++ solution**
    255 
    256 ```
    257 #include <bits/stdc++.h>
    258 
    259 using namespace std;
    260 
    261 int main()
    262 {
    263 	ios_base::sync_with_stdio(0), cin.tie(0);
    264 
    265 	int test;
    266 	cin >> test;
    267 	while (test--)
    268 	{
    269 		int n;
    270 		cin >> n;
    271 		
    272 		int x = 0;
    273 		vector<int> a(n);
    274 		for (auto &i : a)
    275 		{
    276 			cin >> i;
    277 			x ^= i;
    278 		}
    279 
    280 		if (x == 0)
    281 		{
    282 			cout << "DRAW\n";
    283 			continue;
    284 		}
    285 
    286 		for (int k = 30; k >= 0; --k)
    287 			if (x >> k & 1)
    288 			{
    289 				vector<int> f(2);
    290 				for (auto &i : a) ++f[i >> k & 1];
    291 				if (f[1] % 4 == 3 && f[0] % 2 == 0)
    292 					cout << "LOSE\n";
    293 				else
    294 					cout << "WIN\n";
    295 				break;
    296 			}
    297 	}
    298 
    299 	return 0;
    300 }
    301 ```
    302 
    303 **Python solution**
    304 
    305 ```
    306 import sys
    307 input = sys.stdin.readline
    308 
    309 d = { 1: 'WIN', 0: 'LOSE', -1: 'DRAW' }
    310 
    311 def main():
    312     t = int(input())
    313 
    314     for _ in range(t):
    315         n = int(input())
    316         a = map(int, input().split())
    317 
    318         f = [0] * 30
    319 
    320         for x in a:
    321             for b in range(30):
    322                 if x >> b & 1:
    323                     f[b] += 1
    324 
    325         ans = -1
    326         for x in reversed(range(30)):
    327             if f[x] % 2 == 1:
    328                 ans = 0 if f[x] % 4 == 3 and (n - f[x]) % 2 == 0 else 1
    329                 break
    330 
    331         print(d[ans])
    332 
    333 main()
    334 ```
    335 
    336 Problem idea: [Devil](/profile/Devil "Master Devil")
    337 
    338 Solution idea: [Devil](/profile/Devil "Master Devil") and [dcordb](/profile/dcordb "Expert dcordb")
    339 
    340 Tutorial is loading...
    341 
    342 **C++ solution**
    343 
    344 ```
    345 #include <bits/stdc++.h>
    346 
    347 using namespace std;
    348 
    349 const int Alp = 20;
    350 
    351 int main()
    352 {
    353 	ios_base::sync_with_stdio(0), cin.tie(0);
    354 
    355 	int test;
    356 	cin >> test;
    357 	while (test--)
    358 	{
    359 	    int len;
    360 		string a, b;
    361 		cin >> len >> a >> b;
    362 		
    363 		vector<int> adj(Alp);
    364 		vector<vector<int>> G(Alp);
    365 		for (int i = 0; i < len; ++i)
    366 			if (a[i] != b[i])
    367 			{
    368 				adj[a[i]-'a'] |= 1 << (b[i]-'a');
    369 				G[a[i]-'a'].push_back(b[i]-'a');
    370 				G[b[i]-'a'].push_back(a[i]-'a');
    371 			}
    372 
    373 		vector<bool> mark(Alp);
    374 		function<void(int)> dfs = [&](int u)
    375 		{
    376 			mark[u] = true;
    377 			for (auto v : G[u])
    378 				if (!mark[v])
    379 					dfs(v);
    380 		};
    381 
    382 		int comp = 0;
    383 		for (int i = 0; i < Alp; ++i)
    384 			if (!mark[i])
    385 				dfs(i), ++comp;
    386 
    387 		int ans = 0;
    388 		vector<bool> dp(1<<Alp);
    389 		dp[0] = true;
    390 		for (int mask = 0; mask < 1<<Alp; ++mask)
    391 			if (dp[mask])
    392 			{
    393 				ans = max(ans, __builtin_popcount(mask));
    394 				for (int u = 0; u < Alp; ++u)
    395 					if ((~mask >> u & 1) && (adj[u] & mask) == 0)
    396 						dp[mask | 1 << u] = true;
    397 			}
    398 
    399 		cout << 2*Alp - comp - ans << "\n";
    400 	}
    401 
    402 	return 0;
    403 }
    404 ```
    405 
    406 Problem idea: [Devil](/profile/Devil "Master Devil")
    407 
    408 Solution idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr")
    409 
    410 Tutorial is loading...
    411 
    412 **C++ solution**
    413 
    414 ```
    415 #include <bits/stdc++.h>
    416 
    417 #define endl '\n'
    418 
    419 using namespace std;
    420 
    421 int main()
    422 {
    423     ios_base::sync_with_stdio(0);
    424     cin.tie(0);
    425 
    426     int n, m;
    427     cin >> n >> m;
    428 
    429     vector<vector<int>> mat(n, vector<int>(m));
    430 
    431     for (int i = 0; i < n; ++i)
    432         for (int j = 0; j < m; ++j)
    433             cin >> mat[i][j];
    434 
    435     vector<int> h(n * m + 1);
    436     vector<int> v(n * m + 1);
    437 
    438     for (int i = 0; i < n; ++i)
    439     {
    440         int a = 0;
    441         for (int j = 0; j < m; ++j)
    442             a = max(a, mat[i][j]);
    443         h[a] = 1;
    444     }
    445 
    446     for (int i = 0; i < m; ++i)
    447     {
    448         int a = 0;
    449         for (int j = 0; j < n; ++j)
    450             a = max(a, mat[j][i]);
    451         v[a] = 1;
    452     }
    453 
    454     vector<vector<int>> fin(n, vector<int>(m));
    455     queue<pair<int, int>> q;
    456 
    457     int x = -1, y = -1;
    458 
    459     for (int u = n * m; u >= 1; --u)
    460     {
    461         x += h[u];
    462         y += v[u];
    463 
    464         if (h[u] || v[u])
    465         {
    466             fin[x][y] = u;
    467         }
    468         else
    469         {
    470             int qx, qy;
    471             tie(qx, qy) = q.front();
    472             q.pop();
    473             fin[qx][qy] = u;
    474         }
    475 
    476         if (h[u])
    477             for (int i = y - 1; i >= 0; --i)
    478                 q.push({x, i});
    479 
    480         if (v[u])
    481             for (int i = x - 1; i >= 0; --i)
    482                 q.push({i, y});
    483     }
    484 
    485     for (int i = 0; i < n; ++i)
    486         for (int j = 0; j < m; ++j)
    487             cout << fin[i][j] << " \n"[j + 1 == m];
    488 
    489     return 0;
    490 }
    491 ```
    492 
    493 Problem idea: [gilcu3](/profile/gilcu3 "Master gilcu3")
    494 
    495 Solution idea: [gilcu3](/profile/gilcu3 "Master gilcu3") and [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr")
    496 
    497 Tutorial is loading...
    498 
    499 **C++ solution**
    500 
    501 ```
    502 #include <bits/stdc++.h>
    503 
    504 using namespace std;
    505 
    506 const int mod = 1000000007;
    507 
    508 int main()
    509 {
    510 	ios::sync_with_stdio(false), cin.tie(0);
    511 
    512 	string s; cin >> s;
    513 	int n = s.length();
    514 	vector<int> dist(n);
    515 	for (int i = 0; i < n; ++i)
    516 		if (s[i] == '0') dist[i] = (i ? dist[i-1] : 0) + 1;
    517 
    518 	vector<int> dp(n + 2), nxt(n+2, n);
    519 	auto get = [&](int i) { return nxt[i] < n ? dp[nxt[i]] : 0; };
    520 
    521 	for (int i = n-1; i >= 0; --i)
    522 	{
    523 		dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod;
    524 		nxt[dist[i]] = i;
    525 	}
    526 
    527 	int ans = n;
    528 	if (nxt[0] < n)
    529 		ans = ((long long)get(0) * (nxt[0] + 1)) % mod;
    530 	cout << ans << "\n";
    531 
    532 	return 0;
    533 }
    534 ```
    535 
    536 Problem idea: [Devil](/profile/Devil "Master Devil")
    537 
    538 Solution idea: [Devil](/profile/Devil "Master Devil") and [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")
    539 
    540 Tutorial is loading...
    541 
    542 **C++ solution**
    543 
    544 ```
    545 #include <bits/stdc++.h>
    546 
    547 using namespace std;
    548 
    549 template<typename C, typename R = C>
    550 struct dinic
    551 {
    552 	typedef C flow_type;
    553 	typedef R result_type;
    554 
    555 	static_assert(std::is_arithmetic<flow_type>::value, "flow_type must be arithmetic");
    556 	static_assert(std::is_arithmetic<result_type>::value, "result_type must be arithmetic");
    557 
    558 	static const flow_type oo = std::numeric_limits<flow_type>::max();
    559 
    560 	struct edge
    561 	{
    562 		//int src; // not needed, can be deleted to save memory
    563 		int dst;
    564 		int rev;
    565 		flow_type cap, flowp;
    566 
    567 		edge(int src, int dst, int rev, flow_type cap, int flowp) :
    568 			/*src(src),*/ dst(dst), rev(rev), cap(cap), flowp(flowp) {}
    569 	};
    570 
    571 	dinic(int n) : adj(n), que(n), level(n), edge_pos(n), flow_id(0) {}
    572 
    573 	int add_edge(int src, int dst, flow_type cap, flow_type rcap = 0)
    574 	{
    575 		adj[src].emplace_back(src, dst, (int) adj[dst].size(), cap, flow_id++);
    576 		if (src == dst) adj[src].back().rev++;
    577 		adj[dst].emplace_back(dst, src,  (int) adj[src].size() - 1, rcap, flow_id++);
    578 		return (int) adj[src].size() - 1 - (src == dst);
    579 	}
    580 
    581 	inline bool side_of_S(int u) { return level[u] == -1; }
    582 
    583 	result_type max_flow(int source, int sink, vector<flow_type> &flow_e)
    584 	{
    585 		result_type flow = 0;
    586 		while (true)
    587 		{
    588 			int front = 0, back = 0;
    589 			std::fill(level.begin(), level.end(), -1);
    590 			for (level[que[back++] = sink] = 0; front < back && level[source] == -1; ++front)
    591 			{
    592 				int u = que[front];
    593 				for (const edge &e : adj[u])
    594 					if (level[e.dst] == -1 && flow_e[rev(e).flowp] < rev(e).cap)
    595 						level[que[back++] = e.dst] = 1 + level[u];
    596 			}
    597 			if (level[source] == -1)
    598 				break;
    599 			std::fill(edge_pos.begin(), edge_pos.end(), 0);
    600 			std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
    601 			{
    602 				if (from == sink)
    603 					return res;
    604 				for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
    605 				{
    606 					edge &e = adj[from][ept];
    607 					if (flow_e[e.flowp] == e.cap || level[e.dst] + 1 != level[from]) continue;
    608 					flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
    609 					if (push > 0)
    610 					{
    611 						flow_e[e.flowp] += push;
    612 						flow_e[rev(e).flowp] -= push;
    613 						if (flow_e[e.flowp] == e.cap)
    614 							++ept;
    615 						return push;
    616 					}
    617 				}
    618 				return static_cast<flow_type>(0);
    619 			};
    620 			for (flow_type f; (f = find_path(source, oo)) > 0;)
    621 				flow += f;
    622 		}
    623 		return flow;
    624 	}
    625 
    626 	result_type max_flow2(int source, int sink, vector<flow_type> &flow_e)
    627 	{
    628 		result_type flow = 0;
    629 		std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
    630 		{
    631 			level[from] = 1;
    632 			if (from == sink)
    633 				return res;
    634 			for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
    635 			{
    636 				edge &e = adj[from][ept];
    637 				if (level[e.dst] == 1 || flow_e[e.flowp] == e.cap) continue;
    638 				flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
    639 				if (push > 0)
    640 				{
    641 					flow_e[e.flowp] += push;
    642 					flow_e[rev(e).flowp] -= push;
    643 					if (flow_e[e.flowp] == e.cap)
    644 						++ept;
    645 					return push;
    646 				}
    647 			}
    648 			return static_cast<flow_type>(0);
    649 		};
    650 		
    651 		for (bool ok = true; ok; )
    652 		{
    653 			int it = 0;
    654 			std::fill(edge_pos.begin(), edge_pos.end(), 0);
    655 			for (flow_type f; ; ++it)
    656 			{
    657 				std::fill(level.begin(), level.end(), -1);
    658 				f = find_path(source, oo);
    659 				if (f == 0)
    660 				{
    661 					if (it == 0) ok = false;
    662 					break;
    663 				}
    664 				flow += f;
    665 			}
    666 		}
    667 		return flow;
    668 	}
    669 
    670 	int flow_id;
    671 private:
    672 	std::vector<std::vector<edge>> adj;
    673 	std::vector<int> que;
    674 	std::vector<int> level;
    675 	std::vector<int> edge_pos;
    676 
    677 	inline edge& rev(const edge &e) { return adj[e.dst][e.rev]; }
    678 };
    679 
    680 const int inf = 25;
    681 
    682 struct edge
    683 {
    684 	int u, v, w;
    685 };
    686 
    687 mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
    688 
    689 void relabel(int n, vector<edge> &e, int k)
    690 {
    691 	shuffle(e.begin() + k, e.end(), rng);
    692 
    693 	vector<vector<pair<int, int>>> adj(n);
    694 	for (auto &i : e)
    695 		adj[i.u].push_back({ i.v, &i-&e[0] });
    696 
    697 	vector<edge> ne = e;
    698 	vector<int> id(n, -1);
    699 	id[0] = 0;
    700 	id[n-1] = n-1;
    701 	int sz = 1, esz = k;
    702 
    703 	function<void(int)> dfs = [&](int u)
    704 	{
    705 		for (auto &v : adj[u])
    706 		{
    707 			if (v.second >= k)
    708 			{
    709 				ne[esz++] = e[v.second];
    710 				v.second = -1;
    711 			}
    712 			if (id[v.first] == -1)
    713 			{
    714 				id[v.first] = sz++;
    715 				dfs(v.first);
    716 			}
    717 		}
    718 	};
    719 	dfs(0);
    720 	
    721 	for (auto &u : adj)
    722 		for (auto v : u)
    723 			if (v.second >= k)
    724 				ne[esz++] = e[v.second];
    725 	
    726 	for (int i = 0; i < n; ++i)
    727 		if (id[i] == -1)
    728 			id[i] = sz++;
    729 			
    730 	e = ne;
    731 	for (auto &i : e)
    732 	{
    733 		i.u = id[i.u];
    734 		i.v = id[i.v];
    735 	}
    736 }
    737 
    738 struct masks
    739 {
    740 	int x, cost;
    741 	vector<int> flow_e;
    742 	
    743 	bool operator<(const masks &o) const
    744 	{
    745 		return cost < o.cost;
    746 	}
    747 };
    748 
    749 typedef std::chrono::_V2::system_clock::time_point timepoint;
    750 
    751 timepoint get_time()
    752 {
    753 	return std::chrono::high_resolution_clock::now();
    754 }
    755 
    756 int get_elapsed(timepoint t)
    757 {
    758 	return std::chrono::duration_cast<std::chrono::milliseconds>(get_time() - t).count();
    759 }
    760 
    761 int main()
    762 {
    763 	ios_base::sync_with_stdio(0), cin.tie(0);
    764 
    765 	int n, m, k, q;
    766 	cin >> n >> m >> k >> q;
    767 	vector<edge> e(m);
    768 	for (auto &i : e) cin >> i.u >> i.v >> i.w, --i.u, --i.v;
    769 
    770 	vector<int> mask(1 << k, -1);
    771 	
    772 	relabel(n, e, k);
    773 	dinic<int> d(n);
    774 	for (int i = 0; i < m; ++i)
    775 		d.add_edge(e[i].u, e[i].v, ((i < k) ? inf : e[i].w));
    776 
    777 	vector<int> flow_e(d.flow_id);
    778 	for (int i = 0; i < k; ++i)
    779 		flow_e[2*i] = inf;
    780 
    781 	mask[0] = d.max_flow(0, n-1, flow_e);
    782 	
    783 	priority_queue<masks> pq;
    784 	pq.push({ 0, 0, flow_e });
    785 	while (!pq.empty())
    786 	{
    787 		int x = pq.top().x;
    788 		flow_e = pq.top().flow_e;
    789 		pq.pop();
    790 		
    791 		for (int j = 0; j < k; ++j)
    792 			if ((~x >> j & 1) && mask[x | 1 << j] == -1)
    793 			{
    794 				auto n_flow_e = flow_e;
    795 				n_flow_e[2 * j] = 0;
    796 				auto t = get_time();
    797 				mask[x | 1 << j] = mask[x] + d.max_flow2(0, n-1, n_flow_e);
    798 				pq.push({ x | 1 << j, get_elapsed(t), n_flow_e });
    799 			}
    800 	}
    801 
    802 	vector<int> cut(1 << k), bit(1 << k);
    803 	for (int i = 1; i < 1 << k; ++i)
    804 		bit[i] = i & -i;
    805 
    806 	const int U = (1 << k) - 1;
    807 	while (q--)
    808 	{
    809 		for (int i = 0; i < k; ++i)
    810 			cin >> cut[1 << i];
    811 
    812 		int ans = mask[U];
    813 		for (int i = 1; i < 1<<k; ++i)
    814 		{
    815 			cut[i] = cut[i ^ bit[i]] + cut[bit[i]];
    816 			ans = min(ans, cut[i] + mask[U ^ i]);
    817 		}
    818 		cout << ans << "\n";
    819 	}
    820 
    821 	return 0;
    822 }
    823 ```
    824 
    825 Problem idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr")
    826 
    827 Solution idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") and [Devil](/profile/Devil "Master Devil")