oj.uz

답안 #724762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
724762 2023-04-15T23:45:06 Z vjudge1 은행 (IZhO14_bank) C++17
19 / 100
 101 ms 89140 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 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: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 82772 KB Output is correct
2 Correct 31 ms 82756 KB Output is correct
3 Correct 31 ms 82848 KB Output is correct
4 Correct 38 ms 83020 KB Output is correct
5 Correct 101 ms 89140 KB Output is correct
6 Correct 36 ms 82856 KB Output is correct
7 Correct 33 ms 82824 KB Output is correct
8 Correct 95 ms 88484 KB Output is correct
9 Correct 94 ms 88784 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 82844 KB Output is correct
2 Correct 38 ms 82848 KB Output is correct
3 Correct 34 ms 82876 KB Output is correct
4 Incorrect 38 ms 82816 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 82896 KB Output is correct
2 Correct 42 ms 82892 KB Output is correct
3 Incorrect 35 ms 82936 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 82772 KB Output is correct
2 Correct 31 ms 82756 KB Output is correct
3 Correct 31 ms 82848 KB Output is correct
4 Correct 38 ms 83020 KB Output is correct
5 Correct 101 ms 89140 KB Output is correct
6 Correct 36 ms 82856 KB Output is correct
7 Correct 33 ms 82824 KB Output is correct
8 Correct 95 ms 88484 KB Output is correct
9 Correct 94 ms 88784 KB Output is correct
10 Correct 32 ms 82844 KB Output is correct
11 Correct 38 ms 82848 KB Output is correct
12 Correct 34 ms 82876 KB Output is correct
13 Incorrect 38 ms 82816 KB Output isn't correct
14 Halted 0 ms 0 KB -