# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
874355 |
2023-11-16T17:45:19 Z |
cocohearts |
Bank (IZhO14_bank) |
C++11 |
|
74 ms |
8828 KB |
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF 2000000000
#define MOD 1000000007
#define loop(x,n) for(int x = 0; x < n; ++x)
#define iloop(x,a,n) for(int x=a; x<n; ++x)
#define sloop(e,s) for(auto&& e : s)
#define itloop(it,m) for(auto&& it = m.begin(); it!=m.end(); ++it)
#define F first
#define S second
#define PB push_back
#define MP make_pair
// num_paid (inc. current), left_to_pay; num=-1 if impossible
ii DP[1<<20];
int main() {
// ii DP[1<<2];
// freopen("bank.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin >> N >> M;
int salaries[N], notes[M];
loop(i,N) {
cin >> salaries[i];
}
loop(i,M) {
cin >> notes[i];
}
bool solved = false;
loop(bm,1<<M) {
bool works = false;
if (!bm) {
DP[bm] = MP(0,salaries[0]);
continue;
}
loop(ind,M) {
if (bm&1<<ind) {
int prev = bm^1<<ind;
if (DP[prev].S==0) {
if (salaries[DP[prev].F+1]>=notes[ind]) {
DP[bm] = MP(DP[prev].F+1,salaries[DP[prev].F+1]-notes[ind]);
works = true;
}
} else if (DP[prev].F>=0 && notes[ind]<=DP[prev].S) {
DP[bm] = MP(DP[prev].F,DP[prev].S-notes[ind]);
works = true;
}
}
if (works) break;
}
if (!works) {
DP[bm] = MP(-1,-1);
}
if (DP[bm] == MP(N-1,0)) {
solved = true;
cout << "YES";
break;
}
}
if (!solved) cout << "NO";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
504 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
460 KB |
Output is correct |
5 |
Correct |
67 ms |
8580 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
600 KB |
Output is correct |
9 |
Correct |
5 ms |
8536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
2 ms |
348 KB |
Output is correct |
6 |
Correct |
2 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
504 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
460 KB |
Output is correct |
5 |
Correct |
67 ms |
8580 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
600 KB |
Output is correct |
9 |
Correct |
5 ms |
8536 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
1 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
2 ms |
348 KB |
Output is correct |
25 |
Correct |
2 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
468 KB |
Output is correct |
31 |
Correct |
20 ms |
8540 KB |
Output is correct |
32 |
Correct |
12 ms |
8692 KB |
Output is correct |
33 |
Correct |
69 ms |
8564 KB |
Output is correct |
34 |
Correct |
68 ms |
8504 KB |
Output is correct |
35 |
Correct |
73 ms |
8576 KB |
Output is correct |
36 |
Correct |
67 ms |
8528 KB |
Output is correct |
37 |
Correct |
69 ms |
8452 KB |
Output is correct |
38 |
Correct |
69 ms |
8568 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
73 ms |
8664 KB |
Output is correct |
41 |
Correct |
71 ms |
8532 KB |
Output is correct |
42 |
Correct |
53 ms |
8528 KB |
Output is correct |
43 |
Correct |
71 ms |
8528 KB |
Output is correct |
44 |
Correct |
69 ms |
8828 KB |
Output is correct |
45 |
Correct |
0 ms |
344 KB |
Output is correct |
46 |
Correct |
66 ms |
8532 KB |
Output is correct |
47 |
Correct |
71 ms |
8572 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
74 ms |
8568 KB |
Output is correct |
50 |
Correct |
12 ms |
8540 KB |
Output is correct |
51 |
Correct |
67 ms |
8564 KB |
Output is correct |
52 |
Correct |
64 ms |
8580 KB |
Output is correct |
53 |
Correct |
12 ms |
8540 KB |
Output is correct |
54 |
Correct |
12 ms |
8540 KB |
Output is correct |
55 |
Correct |
12 ms |
8536 KB |
Output is correct |
56 |
Correct |
8 ms |
8540 KB |
Output is correct |
57 |
Correct |
9 ms |
8584 KB |
Output is correct |
58 |
Correct |
9 ms |
8540 KB |
Output is correct |