# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
624818 |
2022-08-08T19:20:11 Z |
sam_28 |
Bank (IZhO14_bank) |
C++17 |
|
163 ms |
8640 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define SWAP(type, a, b) \
{ \
const type tmp = a; \
a = b; \
b = tmp; \
}
#define rep(i, l, r) for (ll i = (l); i < (r); i++)
#define per(i, l, r) for (ll i = (l); i >= (r); i--)
#define dbg(x) cout << #x << " = " << x << ln
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define tc \
ll t; \
cin >> t; \
while (t--)
#define godspeed \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define NO cout << "NO" \
<< "\n"
#define YES cout << "YES" \
<< "\n"
#define clr(x, y) memset(x, y, sizeof(x))
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007
template <class T>
bool ckmin(T &a, const T &b)
{
return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const ll inf = 1e9;
const ll llinf = 2e18;
ll MULL(ll a, ll b)
{
a = a % mod;
b = b % mod;
return (((a * b) % mod) + mod) % mod;
}
ll POWER(ll a, ll b)
{
a %= mod;
ll res = 1;
while (b > 0)
{
if (b & 1)
res = MULL(res, a);
a = MULL(a, a);
b >>= 1;
}
return res;
}
void solve()
{
int n, m;
cin >> n >> m;
vi people(n);
for (int i = 0; i < n; i++)
{
cin >> people[i];
}
vi salary(m);
for (int i = 0; i < m; i++)
{
cin >> salary[i];
}
vi people_covered(1 << m, -1);
vi left_money(1 << m);
people_covered[0] = 0;
left_money[0] = 0;
for (int mask = 0; mask < (1 << m); mask++)
{
for (int last = 0; last < m; last++)
{
if (mask & (1 << last))
{
int prevMask = mask ^ (1 << last);
if (people_covered[prevMask] == -1)
{
continue;
}
int newAmt = salary[last] + left_money[prevMask];
int target = people[people_covered[prevMask]];
if (target > newAmt)
{
left_money[mask] = max(left_money[mask], newAmt);
people_covered[mask] = people_covered[prevMask];
}
else if (target == newAmt)
{
left_money[mask] = 0;
people_covered[mask] = people_covered[prevMask] + 1;
}
}
}
}
for (int i = 0; i < (1 << m); i++)
{
if (people_covered[i] == n)
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
return;
}
int main()
{
godspeed;
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
84 ms |
8532 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
372 KB |
Output is correct |
8 |
Correct |
102 ms |
8552 KB |
Output is correct |
9 |
Correct |
124 ms |
8532 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 |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
316 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
368 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
2 ms |
360 KB |
Output is correct |
8 |
Correct |
2 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
340 KB |
Output is correct |
11 |
Correct |
3 ms |
444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
596 KB |
Output is correct |
5 |
Correct |
84 ms |
8532 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
372 KB |
Output is correct |
8 |
Correct |
102 ms |
8552 KB |
Output is correct |
9 |
Correct |
124 ms |
8532 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
368 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
2 ms |
340 KB |
Output is correct |
21 |
Correct |
2 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
340 KB |
Output is correct |
24 |
Correct |
2 ms |
340 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
2 ms |
360 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
2 ms |
340 KB |
Output is correct |
29 |
Correct |
2 ms |
340 KB |
Output is correct |
30 |
Correct |
3 ms |
444 KB |
Output is correct |
31 |
Correct |
150 ms |
8532 KB |
Output is correct |
32 |
Correct |
163 ms |
8532 KB |
Output is correct |
33 |
Correct |
103 ms |
8532 KB |
Output is correct |
34 |
Correct |
79 ms |
8564 KB |
Output is correct |
35 |
Correct |
90 ms |
8548 KB |
Output is correct |
36 |
Correct |
89 ms |
8532 KB |
Output is correct |
37 |
Correct |
84 ms |
8532 KB |
Output is correct |
38 |
Correct |
86 ms |
8532 KB |
Output is correct |
39 |
Correct |
88 ms |
8528 KB |
Output is correct |
40 |
Correct |
94 ms |
8532 KB |
Output is correct |
41 |
Correct |
92 ms |
8576 KB |
Output is correct |
42 |
Correct |
157 ms |
8532 KB |
Output is correct |
43 |
Correct |
91 ms |
8532 KB |
Output is correct |
44 |
Correct |
82 ms |
8436 KB |
Output is correct |
45 |
Correct |
147 ms |
8532 KB |
Output is correct |
46 |
Correct |
115 ms |
8540 KB |
Output is correct |
47 |
Correct |
86 ms |
8532 KB |
Output is correct |
48 |
Correct |
104 ms |
8528 KB |
Output is correct |
49 |
Correct |
76 ms |
8532 KB |
Output is correct |
50 |
Correct |
137 ms |
8516 KB |
Output is correct |
51 |
Correct |
76 ms |
8448 KB |
Output is correct |
52 |
Correct |
90 ms |
8532 KB |
Output is correct |
53 |
Correct |
133 ms |
8528 KB |
Output is correct |
54 |
Correct |
156 ms |
8576 KB |
Output is correct |
55 |
Correct |
139 ms |
8532 KB |
Output is correct |
56 |
Correct |
134 ms |
8576 KB |
Output is correct |
57 |
Correct |
134 ms |
8528 KB |
Output is correct |
58 |
Correct |
130 ms |
8640 KB |
Output is correct |