//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code !
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define endl '\n'
#define eb emplace_back
#define em emplace
#define pb push_back
#define pf push_front
#define pp pop_back
#define fr first
#define sc second
#define sz size
/*vector<bool> f(26 , true) ;
bool va[mn][mn] = {false};
bool vb[mn][mn] = {false};
ll dp[mn][mn];*/
/*
const ll mn = 1771;
ll lch[mn], rch[mn];
vector<ll> ed[mn];
deque<ll> rs[mn];
set<ll> v[mn];
bool us[mn];
pair<ll, ll> ar[mn];
ll prv[mn], rnk[mn];
bool lf[mn];
bool va[mn][mn] = {false};
bool vb[mn][mn] = {false};*/
/*
const ll mn = 5e5+10 ;
const ll mod = 1e9+7;
ll a[mn], fa[mn];
vector<tuple<ll, ll, ll>> ed;
ll find(ll x) {
return (x == fa[x])? x:(fa[x] = find(fa[x]));
}*/
//ll b[400014];
/*
string a[]= {"01" , "1" , "23456789", "0123456789"} ;
const ll mxn = 1e5 + 14 ;
const ll dx[] = {-1 , 0 , 1 , 0} ;
const ll dy[] = {0 , 1 , 0 , -1} ;
vector <ll> adj[mxn] ;
ll p[mxn][2] ;
*/
/*
ll bit(ll n){
for(ll i = 0 ; i < 32 ; i++) {if((! (n& (1 << i))) and n &(1 << ( i + 1))) return(i);}
}
*/
ll n ,m ;
vector<vector<ll>> dp ;
ll eds(ll i1, ll j1, ll i2, ll j2) {
return (ll)(i1 - i2) * (i1 - i2) + (ll)(j1 - j2) * (j1 - j2);
}
db dou(db x) {return x * x ;}
vector<ll> cps(const vector<ll> & arr , ll n) {
vector <ll> ps(n + 1 , 0) ;
for(ll i =0 ; i <n ; i++) ps[i + 1] = ps[i] + arr[i] ;
return ps ;
}
/*
const ll mx = 200014;
ll d[mx] ; ll e[mx];
vector<ll> a[mx];
vector <ll> aa[mx];
const ll md = 998244353;
ll n , k , u , v ;
*/
/*
ll cvp(ll n , ll k ,ll x , const vector<ll> & arr){
vector <ll> ps = cps(arr , n) ;
ll ts = ps[n] ;
ll count = 0 ;
for(ll s = 0 ; s < n ; s++) {
ll sm = 0 ;
for(ll c = 0 ; c < k ; c++) {
for(ll i = s; i < n ; i++) {
sm += arr[i] ;
if(sm >= x) {
count ++ ;
break ;
}
}
}
}
return count ;
}*/
ll nx(string s){
cout << "next" ;
cout.flush();
for(auto i: s) cout << " " << i ;
cout << endl ;
cout.flush() ;
ll n ; cin >> n ;
for(ll i = 1 ; i <= n ;i++) cin >> s ;
return n ;
}
bool ip(const string& s) {
if(s == "1") return false ;
if(s.length() <= 18) {
ll nm = stoll(s) ;
if(nm < 2) return false ;
for(ll i = 2; i * i <= nm ;i++) if(nm % i == 0) return false ;
return true;
}
vector<ll> prm = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
499, 503, 509, 521, 523, 541};
for(ll i : prm){
ll rm = 0 ;
for(char c:s) rm = (rm *10 + (c - '0')) % i ;
if(rm == 0) return false ;
}
return true;
}
/*
double cc(const string& num) {
ll sod = 0;
for (char i : num) sod += i - '0';
double vl = 0;
for (char i : num) vl = vl * 10 + (i - '0');
double c = vl / sod;
return c;
}
*/
/*
ll mmdtv(const string& n) {
ll len = n.size() ;
ll mnr = len - 1;
double mc = 1e18;
for(ll m = 1 ; m < (1 << len) ; m++) {
string r ;
for(ll i = 0 ; i < len ; i++) if(m & (1 << i)) r += n[i] ;
if(!r.empty()) {
double c = cc(r) ;
ll rv = len - r.size();
if(c < mc || (abs(c - mc) < 1e-9 && rv < mnr)) {mc = c;mnr = rv; }
}
}
return mnr;
}
*/
bool sv(ll c , ll i , vector <ll> &arr, vector<vector<ll>> &sm) {
if(i == n) return true ;
if(dp[c][i] != -1) return dp[c][i] ;
for(ll &j : sm[arr[i]]) {
if(j & c) continue ;
if(sv(j | c , i +1 , arr , sm)){ return dp[c][i] = 1 ; return true;}
}
dp[c][i] = 0 ;
return false ;
}
ll gp(ll lv, ll rw, ll cl) {
if (lv == 1) {
if (rw == 1 && cl == 1) return 1;
if (rw == 2 && cl == 2) return 2;
if (rw == 2 && cl == 1) return 3;
return 4;
}
ll hf = 1 << (lv - 1);
ll bc = 1LL << (2 * (lv - 1));
if (rw <= hf && cl <= hf)return gp(lv - 1, rw, cl);
if (rw > hf && cl > hf)return bc + gp(lv - 1, rw - hf, cl - hf);
if (rw > hf && cl <= hf)return 2 * bc + gp(lv - 1, rw - hf, cl);
return 3 * bc + gp(lv - 1, rw, cl - hf);
}
pair<ll , ll> getp(ll lv, ll ps) {
if (lv == 1) {
if (ps == 1) return {1, 1};
if (ps == 2) return {2, 2};
if (ps == 3) return {2, 1};
return {1, 2};
}
ll hf = 1 << (lv - 1);
ll bs = 1LL << (2 * (lv - 1));
if (ps <= bs)return getp(lv - 1, ps);
if (ps <= 2 * bs) {auto p = getp(lv - 1, ps - bs);return {p.fr + hf, p.sc + hf};}
if (ps <= 3 * bs) { auto p = getp(lv - 1, ps - 2 * bs);return {p.fr + hf, p.sc}; }
auto p = getp(lv - 1, ps - 3 * bs);
return {p.fr, p.sc + hf};
}
bool prime(ll n) {
if(n < 2) return false ;
for(ll i =2; i*i <= n ; i++) if(n % i == 0) return false ;
return true ;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(0) ; cout.tie(0);
/*ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (ll i = 0; i < n; i++)cin >> a[i];
if (k == 1) {
ll tt = 0;
for (ll nm : a) tt += nm;
cout << tt << endl;
return 0;
}
ll lm = n -k + 1;
vector<ll> pr(n + 1, 0);
for (ll i = 0; i < n; i++) pr[i + 1] = pr[i] + a[i];
deque<ll> dq;
ll ms = 1e18;
for (ll i = 0; i < n; i++) {
ll cs = max(0LL, i - lm + 1);
while (!dq.empty() && dq.front() < cs) dq.pop_front();
while (!dq.empty() && pr[i] >= pr[dq.back()])dq.pp();
dq.pb(i);
ll cmp = pr[dq.front()];
ll css = pr[i + 1] - cmp;
if (css < ms) ms = css;
}
cout << ms << endl;*/
cin >> n >> m ;
vector <ll> arr(n) ;
vector<ll> b (m) ;
ll mx = 0 ; for(ll &i : arr) cin >> i ;
for(ll &i : b) {cin >> i ; mx += i;}
vector<vector<ll>> sm (mx +1) ;
dp.resize((1 << m) , vector<ll> (n + 1 , -1)) ;
for(ll i = 0 ; i < (1 << m) ;i++) {
ll c= 0 ;
for(ll j = 0 ; j < m ; j++) if(i & (1 << j)) c += b[j] ;
if(c >mx) continue ;
sm[c].pb(i) ;
}
//char s[200014] ;
/*ll t;
cin >>t ;
while(t--) {
ll n ; cin >> n ;
}
*/
/*while(true){ll ans = nx(a[0]) ; ans = nx(a[1]) ; if(ans == 2) break;}
while(true) {ll ans = nx(a[3]) ;if(ans == 1) break ;}
cout << "done" << endl ;
cout.flush() ;*/
//ll t; cin >> t ;
//while(t--){
/*ll n ;
cin >> n ;
ll q ;
cin >> q ;
while(q--) {
string s;
cin >> s ;
if(s == "->") {ll x ,y ; cin >> x >>y ; cout << gp(n , x ,y) << endl ;}
else {ll d ; cin >> d ; pair<ll , ll> p = getp(n , d) ; cout << p.fr << " " << p.sc << endl;}
}*/
/*string n ; cin >> n ;
//cout << mmdtv(n) << endl ;
//i'll try another bad idea
//ok
ll mx = 0 ;
ll count = 0 ;
for(auto i : n) {
if(i == '0') count ++ ;
else mx = max(mx, count + 1) ;
}
cout << n.sz() - mx << endl;*/
for(ll &i :arr) {
if(i > mx) {cout << "NO" << endl ; return 0;}
if(sm[i].empty()) {cout << "NO" << endl ; return 0 ;}
}
if(sv(0 , 0 , arr, sm)) {cout << "YES" << endl;} else cout << "NO" << endl;
return 0 ;
}
# | 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... |