oj.uz

Submission #724761

# Submission time Handle Problem Language Result Execution time Memory
724761 2023-04-15T23:38:33 Z vjudge1 Bank (IZhO14_bank) C++17
19 / 100
 100 ms 89164 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]]){
        if(mask&to==to){
            return dp[mask][u]=solution(mask^to,u+1);
        }
    }
    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>0){
        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:36:19: warning: self-comparison always evaluates to true [-Wtautological-compare]
   36 |         if(mask&to==to){
      |                 ~~^~~~
bank.cpp:36:19: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   36 |         if(mask&to==to){
      |                 ~~^~~~
bank.cpp:37:31: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |             return dp[mask][u]=solution(mask^to,u+1);
      |                    ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bank.cpp: In function 'void solve()':
bank.cpp:64:34: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   64 |     bool res=solution((1<<m)-1,0)<<ln;
      |                                  ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82764 KB Output is correct
2 Correct 32 ms 82832 KB Output is correct
3 Correct 31 ms 82768 KB Output is correct
4 Correct 33 ms 83020 KB Output is correct
5 Correct 99 ms 89164 KB Output is correct
6 Correct 32 ms 82772 KB Output is correct
7 Correct 34 ms 82860 KB Output is correct
8 Correct 100 ms 88564 KB Output is correct
9 Correct 97 ms 88908 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 82896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 82996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82764 KB Output is correct
2 Correct 32 ms 82832 KB Output is correct
3 Correct 31 ms 82768 KB Output is correct
4 Correct 33 ms 83020 KB Output is correct
5 Correct 99 ms 89164 KB Output is correct
6 Correct 32 ms 82772 KB Output is correct
7 Correct 34 ms 82860 KB Output is correct
8 Correct 100 ms 88564 KB Output is correct
9 Correct 97 ms 88908 KB Output is correct
10 Incorrect 31 ms 82896 KB Output isn't correct
11 Halted 0 ms 0 KB -