oj.uz

Submission #537758

# Submission time Handle Problem Language Result Execution time Memory
537758 2022-03-15T13:04:57 Z perchuts Bank (IZhO14_bank) C++17
100 / 100
 808 ms 188392 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

bool dp[20][(1<<20)], mark[20][(1<<20)];
vector<int>a,b;
vector<ii>g[(1<<20)];
int n,m;
int indmax;
bool solve(int i,int mask,int sum=0){
    if(i==n)return 1;
    if(mark[i][mask])return dp[i][mask];
    mark[i][mask] = 1;
    if(sum==a[i])return dp[i][mask] = solve(i+1,mask,0);
    else if(sum>a[i])return dp[i][mask] = 0;
    for(auto [a,b]:g[mask]){
        dp[i][mask]|=solve(i,a,sum+b);
    }
    return dp[i][mask];
}


int main(){_
    cin>>n>>m;
    a.resize(n);b.resize(m);
    sort(all(a));sort(all(b));
    for(auto& x:a)cin>>x;
    for(auto& x:b)cin>>x;
    for(int i=0;i<(1<<m);++i){
        int tmp = 0;
        while(tmp<m){
            if(((1<<tmp)&i)==0)g[i].pb({((1<<tmp)|i),b[tmp]});
            ++tmp;
        }
    }
    cout<<(solve(0,0)?"YES":"NO")<<endl;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 16 ms 25008 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 22 ms 28148 KB Output is correct
5 Correct 326 ms 156332 KB Output is correct
6 Correct 15 ms 24976 KB Output is correct
7 Correct 14 ms 25044 KB Output is correct
8 Correct 459 ms 158144 KB Output is correct
9 Correct 644 ms 158120 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25044 KB Output is correct
2 Correct 15 ms 25008 KB Output is correct
3 Correct 16 ms 24940 KB Output is correct
4 Correct 18 ms 24964 KB Output is correct
5 Correct 15 ms 25140 KB Output is correct
6 Correct 15 ms 25040 KB Output is correct
7 Correct 14 ms 25044 KB Output is correct
8 Correct 14 ms 25036 KB Output is correct
9 Correct 14 ms 24952 KB Output is correct
10 Correct 14 ms 25044 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 26452 KB Output is correct
2 Correct 19 ms 26488 KB Output is correct
3 Correct 19 ms 26708 KB Output is correct
4 Correct 18 ms 26324 KB Output is correct
5 Correct 18 ms 26452 KB Output is correct
6 Correct 19 ms 26372 KB Output is correct
7 Correct 18 ms 26452 KB Output is correct
8 Correct 18 ms 26508 KB Output is correct
9 Correct 19 ms 26620 KB Output is correct
10 Correct 19 ms 26608 KB Output is correct
11 Correct 22 ms 26324 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24916 KB Output is correct
2 Correct 16 ms 25008 KB Output is correct
3 Correct 14 ms 24916 KB Output is correct
4 Correct 22 ms 28148 KB Output is correct
5 Correct 326 ms 156332 KB Output is correct
6 Correct 15 ms 24976 KB Output is correct
7 Correct 14 ms 25044 KB Output is correct
8 Correct 459 ms 158144 KB Output is correct
9 Correct 644 ms 158120 KB Output is correct
10 Correct 14 ms 25044 KB Output is correct
11 Correct 15 ms 25008 KB Output is correct
12 Correct 16 ms 24940 KB Output is correct
13 Correct 18 ms 24964 KB Output is correct
14 Correct 15 ms 25140 KB Output is correct
15 Correct 15 ms 25040 KB Output is correct
16 Correct 14 ms 25044 KB Output is correct
17 Correct 14 ms 25036 KB Output is correct
18 Correct 14 ms 24952 KB Output is correct
19 Correct 14 ms 25044 KB Output is correct
20 Correct 19 ms 26452 KB Output is correct
21 Correct 19 ms 26488 KB Output is correct
22 Correct 19 ms 26708 KB Output is correct
23 Correct 18 ms 26324 KB Output is correct
24 Correct 18 ms 26452 KB Output is correct
25 Correct 19 ms 26372 KB Output is correct
26 Correct 18 ms 26452 KB Output is correct
27 Correct 18 ms 26508 KB Output is correct
28 Correct 19 ms 26620 KB Output is correct
29 Correct 19 ms 26608 KB Output is correct
30 Correct 22 ms 26324 KB Output is correct
31 Correct 613 ms 160216 KB Output is correct
32 Correct 679 ms 162136 KB Output is correct
33 Correct 349 ms 165836 KB Output is correct
34 Correct 326 ms 163540 KB Output is correct
35 Correct 345 ms 163928 KB Output is correct
36 Correct 334 ms 157652 KB Output is correct
37 Correct 332 ms 158276 KB Output is correct
38 Correct 323 ms 156224 KB Output is correct
39 Correct 387 ms 166292 KB Output is correct
40 Correct 352 ms 157172 KB Output is correct
41 Correct 346 ms 157028 KB Output is correct
42 Correct 502 ms 165260 KB Output is correct
43 Correct 334 ms 164264 KB Output is correct
44 Correct 363 ms 156400 KB Output is correct
45 Correct 437 ms 161884 KB Output is correct
46 Correct 405 ms 165188 KB Output is correct
47 Correct 313 ms 158516 KB Output is correct
48 Correct 433 ms 158176 KB Output is correct
49 Correct 308 ms 156840 KB Output is correct
50 Correct 735 ms 188344 KB Output is correct
51 Correct 365 ms 159244 KB Output is correct
52 Correct 331 ms 166656 KB Output is correct
53 Correct 727 ms 173780 KB Output is correct
54 Correct 720 ms 187540 KB Output is correct
55 Correct 778 ms 188312 KB Output is correct
56 Correct 778 ms 188392 KB Output is correct
57 Correct 693 ms 186268 KB Output is correct
58 Correct 808 ms 186472 KB Output is correct