oj.uz

Submission #724767

# Submission time Handle Problem Language Result Execution time Memory
724767 2023-04-15T23:50:32 Z vjudge1 Bank (IZhO14_bank) C++17
19 / 100
 99 ms 89116 KB 
#include<bits/stdc++.h>
#define INF 1e9+7
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define pdd pair<double,double>
#define pipii pair<int,pii>
#define plpll pair<ll,pll>
#define vi vector<int>
#define vvi vector<vi>
#define v3i vector<vvi>
#define v4i vector<v3i>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ins insert
#define ln '\n'
#define all(v) v.begin(),v.end()
using namespace std;

const int up=(1<<20);
int n,m;
vvi total_sum(20001);
int a[20],b[20];
int dp[up][20];

bool solution(int mask,int u){
    if(u==n){
        return true;
    }
   // if(dp[mask][u]!=-1) return dp[mask][u];
    for(auto to:total_sum[a[u]]){
        //cout<<mask<<" "<<to<<ln;
        if(mask&to==to){
            if(solution(mask^to,u+1)){
                return true;
            }
        }
    }
    return false;
}

void solve(){
    //ifstream cin("bank.in");
    //ofstream cout("bank.out");
    memset(dp,-1,sizeof(dp));
    cin>>n>>m;
    for(int i=0;i<n;++i){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    for(int mask=1;mask<(1<<m);++mask){
        int sum=0;
        for(int j=0;j<m;++j){
            if(mask&(1<<j)){
                sum+=b[j];
            }
        }
        //cout<<sum<<" "<<mask<<ln;
        total_sum[sum].eb(mask);
    }
    bool res=solution((1<<m)-1,0)<<ln;
    //cout<<res<<ln;
    if(res){
        cout<<"YES"<<ln;
    }
    else{
        cout<<"NO"<<ln;
    }
    //cin.close();
    //cout.close();
}

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++){
        solve();
    }
}
/*
10 10
0 1 10 100
1 1 5 3
1 7 9 8
0 1 10 9
2 1 2 3
2 9 4
0 1 10 100
1 1 10 2
0 1 10 1000
2 1 5 2
0 1 6
1



0
ll
10
1 2
2 4
4 8
4 9
2 5
1 3
3 6
6 10
3 7
*/

Compilation message

bank.cpp: In function 'bool solution(int, int)':
bank.cpp:37:19: warning: self-comparison always evaluates to true [-Wtautological-compare]
   37 |         if(mask&to==to){
      |                 ~~^~~~
bank.cpp:37:19: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   37 |         if(mask&to==to){
      |                 ~~^~~~
bank.cpp: In function 'void solve()':
bank.cpp:67:34: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   67 |     bool res=solution((1<<m)-1,0)<<ln;
      |                                  ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 82760 KB Output is correct
2 Correct 33 ms 82836 KB Output is correct
3 Correct 35 ms 82836 KB Output is correct
4 Correct 39 ms 83040 KB Output is correct
5 Correct 99 ms 89116 KB Output is correct
6 Correct 31 ms 82900 KB Output is correct
7 Correct 34 ms 82868 KB Output is correct
8 Correct 98 ms 88556 KB Output is correct
9 Correct 98 ms 88852 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 82776 KB Output is correct
2 Correct 31 ms 82748 KB Output is correct
3 Correct 32 ms 82800 KB Output is correct
4 Incorrect 35 ms 82860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 82940 KB Output is correct
2 Correct 34 ms 82968 KB Output is correct
3 Incorrect 35 ms 82972 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 82760 KB Output is correct
2 Correct 33 ms 82836 KB Output is correct
3 Correct 35 ms 82836 KB Output is correct
4 Correct 39 ms 83040 KB Output is correct
5 Correct 99 ms 89116 KB Output is correct
6 Correct 31 ms 82900 KB Output is correct
7 Correct 34 ms 82868 KB Output is correct
8 Correct 98 ms 88556 KB Output is correct
9 Correct 98 ms 88852 KB Output is correct
10 Correct 30 ms 82776 KB Output is correct
11 Correct 31 ms 82748 KB Output is correct
12 Correct 32 ms 82800 KB Output is correct
13 Incorrect 35 ms 82860 KB Output isn't correct
14 Halted 0 ms 0 KB -