| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 442615 | leaked | 은행 (IZhO14_bank) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define vec vector
#define sz(x) ( int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
auto rng=bind(uniform_int_distribution<int>(1,32000),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=1e3+1;
bitset<N>emp,my,pref[N];
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vec<int>a(n),b(m);
for(auto &z : a)
cin>>z;
for(auto &z : b)
cin>>z;
sort(all(a));
sort(rall(b));
for(int i=0;i<n;i++){
/// now we need to do
my&=emp;my[0]=1;
vec<int>nb;
m=sz(b);
for(int j=0;j<m;j++){
pref[j]=my;
my|=(my<<b[j]);
}
int s=a[i];
if(!my[s]){
cout<<"NO";
return 0;
}
for(int j=m-1;j>=0;j--){
if(s>=b[j] && pref[j][s-b[j]]) s-=b[j];
else nb.pb(b[j]);
}
swap(b,nb);
}
cout<<"YES";
return 0;
}
/*
2 3
5 4
5 1 4
*/