oj.uz

Submission #724763

# Submission time Handle Problem Language Result Execution time Memory
724763 2023-04-15T23:45:54 Z vjudge1 Bank (IZhO14_bank) C++17
19 / 100
 117 ms 89112 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 dp[mask][u]=true;
            }
        }
    }
    return dp[mask][u]=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:39:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   39 |                 return dp[mask][u]=true;
      |                        ~~~~~~~~~~~^~~~~
bank.cpp:43:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   43 |     return dp[mask][u]=false;
      |            ~~~~~~~~~~~^~~~~~
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 33 ms 82772 KB Output is correct
2 Correct 37 ms 82844 KB Output is correct
3 Correct 33 ms 82812 KB Output is correct
4 Correct 39 ms 83028 KB Output is correct
5 Correct 98 ms 89112 KB Output is correct
6 Correct 34 ms 82824 KB Output is correct
7 Correct 33 ms 82780 KB Output is correct
8 Correct 93 ms 88500 KB Output is correct
9 Correct 117 ms 88828 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82844 KB Output is correct
2 Correct 33 ms 82852 KB Output is correct
3 Correct 32 ms 82800 KB Output is correct
4 Incorrect 33 ms 82760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82924 KB Output is correct
2 Correct 35 ms 82896 KB Output is correct
3 Incorrect 34 ms 83028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82772 KB Output is correct
2 Correct 37 ms 82844 KB Output is correct
3 Correct 33 ms 82812 KB Output is correct
4 Correct 39 ms 83028 KB Output is correct
5 Correct 98 ms 89112 KB Output is correct
6 Correct 34 ms 82824 KB Output is correct
7 Correct 33 ms 82780 KB Output is correct
8 Correct 93 ms 88500 KB Output is correct
9 Correct 117 ms 88828 KB Output is correct
10 Correct 32 ms 82844 KB Output is correct
11 Correct 33 ms 82852 KB Output is correct
12 Correct 32 ms 82800 KB Output is correct
13 Incorrect 33 ms 82760 KB Output isn't correct
14 Halted 0 ms 0 KB -