# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
475901 | 2021-09-24T11:27:55 Z | mat_v | Bank (IZhO14_bank) | C++14 | 343 ms | 16836 KB |
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i)) #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i)) #define mod 998244353 #define xx first #define yy second #define all(a) (a).begin(), (a).end() #define pb push_back #define ll long long #define pii pair<int,int> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less) mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int n,m; int a[25]; int b[25]; int dp[(1<<20) + 5]; int ost[(1<<20) + 5]; int kol[(1<<20) + 5]; int niz[(1<<20) + 5]; bool cmp(int a, int b){return kol[a] < kol[b];} int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; ff(i,0,n - 1)cin >> a[i]; ff(i,0,m - 1)cin >> b[i]; ff(i,0,(1<<m) - 1){ niz[i] = i; ff(j,0,m - 1){ if((1<<j)&i)kol[i]++; } } sort(niz, niz + (1<<m), cmp); dp[0] = -1; ff(r,1,(1<<m) - 1){ int i = niz[r]; dp[i] = -1; int sum = 0; ff(j,0,m - 1){ if((1<<j)&i){ sum += b[j]; } } ost[i] = sum; ff(j,0,m - 1){ if((1<<j)&i){ int dkl = dp[i^(1<<j)]; int kol = ost[i^(1<<j)] + b[j]; if(a[dkl + 1] == kol){ dkl++; kol = 0; } if(dkl > dp[i]){ dp[i] = dkl; ost[i] = kol; } } } } if(dp[(1<<m) - 1] >= n-1)cout << "YES\n"; else cout << "NO\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 9 ms | 844 KB | Output is correct |
5 | Correct | 326 ms | 16716 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 334 ms | 16768 KB | Output is correct |
9 | Correct | 315 ms | 16620 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 328 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 336 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 584 KB | Output is correct |
2 | Correct | 5 ms | 712 KB | Output is correct |
3 | Correct | 4 ms | 584 KB | Output is correct |
4 | Correct | 4 ms | 588 KB | Output is correct |
5 | Correct | 4 ms | 588 KB | Output is correct |
6 | Correct | 5 ms | 588 KB | Output is correct |
7 | Correct | 4 ms | 588 KB | Output is correct |
8 | Correct | 4 ms | 588 KB | Output is correct |
9 | Correct | 4 ms | 588 KB | Output is correct |
10 | Correct | 4 ms | 588 KB | Output is correct |
11 | Correct | 4 ms | 588 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 9 ms | 844 KB | Output is correct |
5 | Correct | 326 ms | 16716 KB | Output is correct |
6 | Correct | 1 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 334 ms | 16768 KB | Output is correct |
9 | Correct | 315 ms | 16620 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 1 ms | 332 KB | Output is correct |
12 | Correct | 1 ms | 328 KB | Output is correct |
13 | Correct | 1 ms | 332 KB | Output is correct |
14 | Correct | 1 ms | 336 KB | Output is correct |
15 | Correct | 1 ms | 332 KB | Output is correct |
16 | Correct | 1 ms | 332 KB | Output is correct |
17 | Correct | 1 ms | 332 KB | Output is correct |
18 | Correct | 1 ms | 332 KB | Output is correct |
19 | Correct | 1 ms | 332 KB | Output is correct |
20 | Correct | 5 ms | 584 KB | Output is correct |
21 | Correct | 5 ms | 712 KB | Output is correct |
22 | Correct | 4 ms | 584 KB | Output is correct |
23 | Correct | 4 ms | 588 KB | Output is correct |
24 | Correct | 4 ms | 588 KB | Output is correct |
25 | Correct | 5 ms | 588 KB | Output is correct |
26 | Correct | 4 ms | 588 KB | Output is correct |
27 | Correct | 4 ms | 588 KB | Output is correct |
28 | Correct | 4 ms | 588 KB | Output is correct |
29 | Correct | 4 ms | 588 KB | Output is correct |
30 | Correct | 4 ms | 588 KB | Output is correct |
31 | Correct | 317 ms | 16632 KB | Output is correct |
32 | Correct | 327 ms | 16648 KB | Output is correct |
33 | Correct | 322 ms | 16728 KB | Output is correct |
34 | Correct | 326 ms | 16780 KB | Output is correct |
35 | Correct | 330 ms | 16776 KB | Output is correct |
36 | Correct | 332 ms | 16632 KB | Output is correct |
37 | Correct | 315 ms | 16768 KB | Output is correct |
38 | Correct | 321 ms | 16720 KB | Output is correct |
39 | Correct | 330 ms | 16760 KB | Output is correct |
40 | Correct | 321 ms | 16704 KB | Output is correct |
41 | Correct | 323 ms | 16772 KB | Output is correct |
42 | Correct | 323 ms | 16644 KB | Output is correct |
43 | Correct | 322 ms | 16664 KB | Output is correct |
44 | Correct | 331 ms | 16648 KB | Output is correct |
45 | Correct | 334 ms | 16704 KB | Output is correct |
46 | Correct | 324 ms | 16820 KB | Output is correct |
47 | Correct | 319 ms | 16704 KB | Output is correct |
48 | Correct | 339 ms | 16836 KB | Output is correct |
49 | Correct | 329 ms | 16656 KB | Output is correct |
50 | Correct | 321 ms | 16600 KB | Output is correct |
51 | Correct | 339 ms | 16708 KB | Output is correct |
52 | Correct | 321 ms | 16708 KB | Output is correct |
53 | Correct | 336 ms | 16744 KB | Output is correct |
54 | Correct | 343 ms | 16836 KB | Output is correct |
55 | Correct | 327 ms | 16760 KB | Output is correct |
56 | Correct | 321 ms | 16708 KB | Output is correct |
57 | Correct | 326 ms | 16672 KB | Output is correct |
58 | Correct | 323 ms | 16648 KB | Output is correct |