이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define fi first
#define se second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
using namespace std;
const int sz = 1e6+6;
const ll inf = 1000000005;
ll a[sz], b[sz];
void solve(){
ll n,m,i,mask;
cin>>n>>m;
vector<pair<ll,ll>> dp((1<<m), {inf,0});
for(i=0;i<n;i++){
cin>>a[i];
}
for(i=0;i<m;i++){
cin>>b[i];
}
dp[0] = {0,0};
for(i=0;i<(1<<m);i++){
for(mask=0;mask<m;mask++){
if(i & (1<<mask)){continue;}
pair<ll,ll> cur = dp[i];
if(cur.fi == inf){break;}
ll f = cur.fi, s = cur.se;
s += b[mask];
if(s > a[f]){continue;}
if(s == a[f]){
f++;
if(f == n){
cout << "YES" << endl;
return ;
}
s=0;
}
if(mpr(f,s) < dp[i | (1<<mask)]){
dp[i | (1<<mask)] = {f,s};
}
}
}
cout << "NO" << endl;
}
int main(){
ll t=1;
//cin>>t;
while(t--){
solve();
}
}
/*
6 3
1 2 3 4 5 6
2
1 3 4 6
2 1 5 4
7 3
3 1 5 6 2 4 7
1
2 1 4 3
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |