# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
724760 | 2023-04-15T23:37:32 Z | vjudge1 | 은행 (IZhO14_bank) | C++17 | 33 ms | 82892 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 82892 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 31 ms | 82788 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 82784 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 82892 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |