# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
732158 | 2023-04-28T14:26:54 Z | Doublade | Bank (IZhO14_bank) | C++17 | 131 ms | 16760 KB |
/* Author: Pieck */ #include<bits/stdc++.h> using namespace std; using namespace chrono; #pragma GCC optimize("-O2") typedef long long ll; typedef long double lld; typedef unsigned long long ull; typedef vector<int> vi; typedef pair<int, int> pi; typedef vector<ll> vl; typedef pair<ll, ll> pl; typedef vector<vector<ll>> matrix; #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #define time__(d) \ for ( \ auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \ blockTime.second; \ debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \ ) #define F first #define S second #define PB push_back #define PPB pop_back #define MP make_pair #define all(c) c.begin(), c.end() #define f(i,a,b) for(ll i=a; i<b; i++) #define rep(i,n) f(i,0,n) #define fd(i, b, a) for(ll i=b; i>=a; i--) #define repr(i,n) fd(i, n-1, 0) #define tr(c,i) for(typeof(c).begin() i = c.begin(); i != c.end(); i++) #define present(c,x) (c.find(x) != c.end()) //for set and map #define cpresent(c,x) (find(all(c),x) != c.end()) //for vectors #define ps(num, places) fixed<<setprecision(places)<<num //use as cout<<ps(x, y)<<"\n"; #define sz(x) (ll)(x).size() void setIO() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } void usaco(string filename) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } template <typename T> void amax(T &a, T b) { a = max(a, b); } template <typename T> void amin(T &a, T b) { a = min(a, b); } const lld epsilon = 1e-9; const ll MOD = 1e9+7; const ll INF = 1e9; bool comp(ll a, ll b) { return (a > b); } ll POW(ll a, ll b) { ll res = 1; while(b>0) { if(b&1) res *= a; a *= a; b >>= 1; } return res; } ll binpow(ll a, ll b, ll p=MOD) { ll res = 1; a %= p; while(b>0) { if(b&1) (res *= a)%=p; (a *= a)%=p; b >>= 1; a %= p; res %= p; } return res; } void runcase() { ll n, m; cin >> n >> m; vl a(n), b(m); rep(i, n) cin >> a[i]; rep(i, m) cin >> b[i]; ll LIM = 1<<m; vl covered(LIM, -1), leftover(LIM, -1); // covered[i] = how many prefix salary values can be paid covered[0] = leftover[0] = 0; f(mask, 1, LIM) { rep(i, m) { if(!(mask&(1<<i))) continue; ll prevState = mask^(1<<i); if(covered[prevState]==-1) continue; ll leftAmt = leftover[prevState]+b[i]; ll targetVal = a[covered[prevState]]; if(leftAmt<targetVal) { covered[mask] = covered[prevState]; leftover[mask] = leftAmt; }else if(leftAmt==targetVal) { covered[mask] = 1+covered[prevState]; leftover[mask] = 0; } } if(covered[mask]==n) { cout<<"YES\n"; return; } } cout<<"NO\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); #ifndef ONLINE_JUDGE // setIO(); // usaco(""); #endif time__("Main") { ll tests = 1; // cin >> tests; while(tests--) { runcase(); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 320 KB | Output is correct |
4 | Correct | 1 ms | 724 KB | Output is correct |
5 | Correct | 81 ms | 16736 KB | Output is correct |
6 | Correct | 1 ms | 324 KB | Output is correct |
7 | Correct | 1 ms | 320 KB | Output is correct |
8 | Correct | 8 ms | 16704 KB | Output is correct |
9 | Correct | 116 ms | 16732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 316 KB | Output is correct |
5 | Correct | 1 ms | 320 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 1 ms | 316 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 468 KB | Output is correct |
2 | Correct | 2 ms | 596 KB | Output is correct |
3 | Correct | 2 ms | 568 KB | Output is correct |
4 | Correct | 2 ms | 596 KB | Output is correct |
5 | Correct | 2 ms | 468 KB | Output is correct |
6 | Correct | 2 ms | 468 KB | Output is correct |
7 | Correct | 2 ms | 596 KB | Output is correct |
8 | Correct | 1 ms | 596 KB | Output is correct |
9 | Correct | 2 ms | 596 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 468 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 320 KB | Output is correct |
4 | Correct | 1 ms | 724 KB | Output is correct |
5 | Correct | 81 ms | 16736 KB | Output is correct |
6 | Correct | 1 ms | 324 KB | Output is correct |
7 | Correct | 1 ms | 320 KB | Output is correct |
8 | Correct | 8 ms | 16704 KB | Output is correct |
9 | Correct | 116 ms | 16732 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 316 KB | Output is correct |
14 | Correct | 1 ms | 320 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 316 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 2 ms | 468 KB | Output is correct |
21 | Correct | 2 ms | 596 KB | Output is correct |
22 | Correct | 2 ms | 568 KB | Output is correct |
23 | Correct | 2 ms | 596 KB | Output is correct |
24 | Correct | 2 ms | 468 KB | Output is correct |
25 | Correct | 2 ms | 468 KB | Output is correct |
26 | Correct | 2 ms | 596 KB | Output is correct |
27 | Correct | 1 ms | 596 KB | Output is correct |
28 | Correct | 2 ms | 596 KB | Output is correct |
29 | Correct | 1 ms | 468 KB | Output is correct |
30 | Correct | 2 ms | 468 KB | Output is correct |
31 | Correct | 113 ms | 16724 KB | Output is correct |
32 | Correct | 117 ms | 16724 KB | Output is correct |
33 | Correct | 83 ms | 16736 KB | Output is correct |
34 | Correct | 76 ms | 16736 KB | Output is correct |
35 | Correct | 94 ms | 16736 KB | Output is correct |
36 | Correct | 91 ms | 16748 KB | Output is correct |
37 | Correct | 82 ms | 16736 KB | Output is correct |
38 | Correct | 72 ms | 16724 KB | Output is correct |
39 | Correct | 7 ms | 16724 KB | Output is correct |
40 | Correct | 79 ms | 16736 KB | Output is correct |
41 | Correct | 76 ms | 16736 KB | Output is correct |
42 | Correct | 131 ms | 16760 KB | Output is correct |
43 | Correct | 90 ms | 16724 KB | Output is correct |
44 | Correct | 81 ms | 16740 KB | Output is correct |
45 | Correct | 8 ms | 16724 KB | Output is correct |
46 | Correct | 97 ms | 16704 KB | Output is correct |
47 | Correct | 77 ms | 16740 KB | Output is correct |
48 | Correct | 9 ms | 16724 KB | Output is correct |
49 | Correct | 80 ms | 16736 KB | Output is correct |
50 | Correct | 110 ms | 16732 KB | Output is correct |
51 | Correct | 74 ms | 16732 KB | Output is correct |
52 | Correct | 91 ms | 16740 KB | Output is correct |
53 | Correct | 130 ms | 16732 KB | Output is correct |
54 | Correct | 118 ms | 16700 KB | Output is correct |
55 | Correct | 106 ms | 16736 KB | Output is correct |
56 | Correct | 106 ms | 16740 KB | Output is correct |
57 | Correct | 110 ms | 16732 KB | Output is correct |
58 | Correct | 107 ms | 16736 KB | Output is correct |