# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
725057 | 2023-04-16T15:38:09 Z | thefless | Bank (IZhO14_bank) | C++14 | 96 ms | 8640 KB |
#include<bits/stdc++.h> using namespace std; #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define Times cerr << "time: " << clock() / 1000.0 << endl #define fi first #define base 31 #define sz(x) (int)(x).size() #define se second #define ll long long #define mp make_pair #define pb push_back #define pii pair<int, int> #define all(x) (x).begin(), (x).end() #define task "name" const int oo = 1e9 + 7; const ll loo = (ll)1e18 + 7; const ll MOD = 1e9 + 7; const int MOD2 = 1e9 + 696969; const int N = 2e5 + 5; const int BASE = 10; template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;} template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;} int n,m,a[N],b[N],dp[(1 << 20) + 7],to[(1 << 20) + 7]; void Solve() { cin>>n>>m; for(int i = 1 ; i <= n ; i++) cin>>a[i]; for(int i = 0 ; i < m ; i++) cin>>b[i]; memset(dp,-1,sizeof dp); memset(to,-1,sizeof to); dp[0]=0; to[0]=1; for(int mask = 0 ; mask < (1 << m) ; mask++){ for(int cur = 0 ; cur < m ; cur++){ if(BIT(mask,cur) || dp[mask] == -1) continue; if(dp[mask] + b[cur] == a[to[mask]]){ dp[(mask | (1 << cur))] = 0; to[(mask | (1 << cur))] = to[mask]+1; } if(dp[mask] + b[cur] < a[to[mask]]){ dp[(mask | (1 << cur))] = dp[mask] + b[cur]; to[(mask | (1 << cur))] = to[mask]; } } if(to[mask] > n) return void(cout<<"YES"); } cout<<"NO"; } void file(){ if( fopen(task".inp","r")){ freopen(task".inp" , "r" , stdin); freopen(task".bug" , "w" , stderr); freopen(task".out" , "w" , stdout); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); file(); int T = 1; // cin >> T; while(T--) { Solve(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8532 KB | Output is correct |
2 | Correct | 4 ms | 8532 KB | Output is correct |
3 | Correct | 4 ms | 8532 KB | Output is correct |
4 | Correct | 4 ms | 8516 KB | Output is correct |
5 | Correct | 64 ms | 8532 KB | Output is correct |
6 | Correct | 4 ms | 8532 KB | Output is correct |
7 | Correct | 4 ms | 8520 KB | Output is correct |
8 | Correct | 4 ms | 8532 KB | Output is correct |
9 | Correct | 70 ms | 8640 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8532 KB | Output is correct |
2 | Correct | 4 ms | 8532 KB | Output is correct |
3 | Correct | 4 ms | 8532 KB | Output is correct |
4 | Correct | 4 ms | 8520 KB | Output is correct |
5 | Correct | 4 ms | 8532 KB | Output is correct |
6 | Correct | 4 ms | 8532 KB | Output is correct |
7 | Correct | 4 ms | 8512 KB | Output is correct |
8 | Correct | 4 ms | 8532 KB | Output is correct |
9 | Correct | 6 ms | 8532 KB | Output is correct |
10 | Correct | 4 ms | 8520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 8516 KB | Output is correct |
2 | Correct | 5 ms | 8524 KB | Output is correct |
3 | Correct | 7 ms | 8520 KB | Output is correct |
4 | Correct | 4 ms | 8532 KB | Output is correct |
5 | Correct | 5 ms | 8532 KB | Output is correct |
6 | Correct | 7 ms | 8520 KB | Output is correct |
7 | Correct | 5 ms | 8532 KB | Output is correct |
8 | Correct | 4 ms | 8532 KB | Output is correct |
9 | Correct | 5 ms | 8524 KB | Output is correct |
10 | Correct | 4 ms | 8532 KB | Output is correct |
11 | Correct | 5 ms | 8516 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 8532 KB | Output is correct |
2 | Correct | 4 ms | 8532 KB | Output is correct |
3 | Correct | 4 ms | 8532 KB | Output is correct |
4 | Correct | 4 ms | 8516 KB | Output is correct |
5 | Correct | 64 ms | 8532 KB | Output is correct |
6 | Correct | 4 ms | 8532 KB | Output is correct |
7 | Correct | 4 ms | 8520 KB | Output is correct |
8 | Correct | 4 ms | 8532 KB | Output is correct |
9 | Correct | 70 ms | 8640 KB | Output is correct |
10 | Correct | 5 ms | 8532 KB | Output is correct |
11 | Correct | 4 ms | 8532 KB | Output is correct |
12 | Correct | 4 ms | 8532 KB | Output is correct |
13 | Correct | 4 ms | 8520 KB | Output is correct |
14 | Correct | 4 ms | 8532 KB | Output is correct |
15 | Correct | 4 ms | 8532 KB | Output is correct |
16 | Correct | 4 ms | 8512 KB | Output is correct |
17 | Correct | 4 ms | 8532 KB | Output is correct |
18 | Correct | 6 ms | 8532 KB | Output is correct |
19 | Correct | 4 ms | 8520 KB | Output is correct |
20 | Correct | 5 ms | 8516 KB | Output is correct |
21 | Correct | 5 ms | 8524 KB | Output is correct |
22 | Correct | 7 ms | 8520 KB | Output is correct |
23 | Correct | 4 ms | 8532 KB | Output is correct |
24 | Correct | 5 ms | 8532 KB | Output is correct |
25 | Correct | 7 ms | 8520 KB | Output is correct |
26 | Correct | 5 ms | 8532 KB | Output is correct |
27 | Correct | 4 ms | 8532 KB | Output is correct |
28 | Correct | 5 ms | 8524 KB | Output is correct |
29 | Correct | 4 ms | 8532 KB | Output is correct |
30 | Correct | 5 ms | 8516 KB | Output is correct |
31 | Correct | 81 ms | 8520 KB | Output is correct |
32 | Correct | 96 ms | 8516 KB | Output is correct |
33 | Correct | 66 ms | 8516 KB | Output is correct |
34 | Correct | 60 ms | 8532 KB | Output is correct |
35 | Correct | 58 ms | 8532 KB | Output is correct |
36 | Correct | 59 ms | 8532 KB | Output is correct |
37 | Correct | 60 ms | 8524 KB | Output is correct |
38 | Correct | 67 ms | 8532 KB | Output is correct |
39 | Correct | 4 ms | 8532 KB | Output is correct |
40 | Correct | 61 ms | 8516 KB | Output is correct |
41 | Correct | 58 ms | 8532 KB | Output is correct |
42 | Correct | 87 ms | 8516 KB | Output is correct |
43 | Correct | 63 ms | 8532 KB | Output is correct |
44 | Correct | 75 ms | 8532 KB | Output is correct |
45 | Correct | 6 ms | 8532 KB | Output is correct |
46 | Correct | 78 ms | 8532 KB | Output is correct |
47 | Correct | 57 ms | 8516 KB | Output is correct |
48 | Correct | 4 ms | 8532 KB | Output is correct |
49 | Correct | 60 ms | 8524 KB | Output is correct |
50 | Correct | 83 ms | 8532 KB | Output is correct |
51 | Correct | 64 ms | 8532 KB | Output is correct |
52 | Correct | 61 ms | 8520 KB | Output is correct |
53 | Correct | 91 ms | 8532 KB | Output is correct |
54 | Correct | 82 ms | 8520 KB | Output is correct |
55 | Correct | 81 ms | 8532 KB | Output is correct |
56 | Correct | 95 ms | 8532 KB | Output is correct |
57 | Correct | 83 ms | 8516 KB | Output is correct |
58 | Correct | 77 ms | 8532 KB | Output is correct |