/*
.:-=++***#***+=:.
.:-==+**##**%########***#####*=:.
.-+#%%#*****############**#******#####+=:
.-*%#####********###########*********#######*+-:
:+#######**********########*****+********##########+-.
:+##########**###******##********************###########+:
:+##########*****#*******###**********************###***####*:
.=###########***###*******#***************************#****#####*:
:*#################******************************************######=
-###################***************+****************************#####*:
.=###################******************************************#****#####+.
:*###################*******************************+************#*****#####:
=#############**######*****#*******************++***++++++***************#####=
.*###########******####*****#************+++*+**+++***++++++++***#**********#####+
-############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####*
=############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*.
.+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*.
.*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*.
.:-: .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*.
.--:++=+. .**. ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*:
:++===== .**. -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=:
.-=++= =*. +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+:
. .#. .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+:
-- -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-.
-=+++-. = +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=:
.++====++ = ####################**##*****###***#+****#=#**** .+*###************+ ## +***######****##########+--+#%%%%+:
.---:=+======+: +. ##################%#***#*****####****#**#+-####. .+###***##*******# .#: :***########***##%%%####%#=. .:=*%%
---==++=======+= -= .%#################%****#*****######-#*##*.=%#*. +=---:::.......: =: =**#########***#%%%%%%%%%%%=. .-
:-:===========+= .#. :%################%%****#*****#####= :-+***#*=. .*#########%%#**#*=%%%%%%%%%%=.
.---=========+= :*. -#################%%****#*****%#+-.-*#%%%@###*= +##########%%%***:+-#%%%#####*:
.:=++++====+- =*.=###%############%@%****#*****#. =###%%%@@@+ ###########%%%%#*#: -*########=
..:::::-. +*+###%####%######%%+******#****#=##= -@@@@@@@+ =*###########%%%%##+ :*#######+
=%##+%####%######%+.******#*****%%#-:+@@@@%-=* +..###########%##%%%*. -#######
%##=#####%###%%#%:=******#*****%*.**##*+=: . -+**####*=: - .=###############%%*: .+#####
.%###%########%%%%:.#*****##*****= .+: . :-::.:--=++- : .-*##################+: :####
:##.*###########%@# #************+ .:.-==-- . +**###+*##############*: .*##
-%- ############%@@-#*###*#=##***#. :. =*++*#**++*##############*- .##
=# ############@@@######*#:###*##= :..+*++++***+++++*##############=.+#
+: ###########%@%%%%######.=###### .=+#+++++++***+++++****##############
.+ *##########%%%%%%######::######= =+++#*+++++++*#+++++******###########
+: =%#%######%%%##%@######:-+######. .:------== :*++++**+++++++*#*+++++********#######
-* :%%%%#####%%%##%%%#####***######* -=--------=: -*+++++++*++++++++*#**+++*=:=******+==*
.*+ +%%%%###%%####%%%#####**+#######= -........:=: -++++++++++*#**##***+******++- .-******=.
-*= *%%%%##%%%%%%%#%#####**++#######. :.........- .=#%%%######%##########%#+*******. .-++++*+
-*+ .*%%%%#%%#######%#####*++++######*: ......... :=#%@@%%%%%%#################*++*****=. .-++++
:**. :###%%%#%%########%####*++++*#######=-:.. -+#%%%###########################++++****#=. .-++
-*+ .######%%%%#########%###@@@%%%%######+...:----:. :*%################################%*+++++*+###- .+
:*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+. .
-+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*. =##+
+#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++ -##.
=%**********#######%%###############%*#####=...=. . :-=-: .###############%#******####%#####+= +*
*#************#############%%#######**+*%####-.- .-:=##############%*********##%#######=: .+.
*#****************##**######%%%###*: ::*#####: -:: .-+####%%%####%*********#%##########*-:
=#***********************######%*- .--:=:. =. :--: .-=*###%###*********#######*#######+-
.#**************************###= .:. ::... .=. +***#%##*******#########***#######+:
=##**************************: :-:--. .. .+..... + =******#%#####%##########***#####**#
####**********************+. . :#########+-=:.... -: +***********##%%#***######****##****
.#%####******************- *##########*:....... ...:. #**************##*********###*##****
:#%@%%%###************* =#*******####+....... :-. *#***************%************#%#****
.#**###%%%%%######****#. =#***********#=....:-. :*#****************##*************####*
*#**#****#####%%%%##### =#*************+=: .=-::..:-*#*****************##*****************##
-#***#*******######%%%%= :=*#**********: ... ##*##%##*******************#********************
.%*****#*********######%. ....:-=*- :++: =#****##%####*************###********************
:. +#*****#**********####%+ ..-*#***#+=##*******##%%###********####*********************
.:-:. .%#*****#**********#%%%* :=+**##########******###********#%%%%%%##****###***********************
-- =%#******#*********@#%%-. :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####*************************
=-. .=. ##*******#********#%#**###*+=-:.: -######%##%###%####%%%%%##########%####%%%%##%*************####************
==== .= :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####***********
==== -: *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####**********
:+=+. = .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######*********
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast","unroll-loops","inline","omit-frame-pointer")
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using mll = map<ll, ll>;
using sll = set<ll>;
using sc = set<char>;
typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
cheese;
#define printv(v) {for(auto &elem:v){cout<<elem<<" ";}cout<<endl;}
#define printg(g) {for(auto &row:g){printv(row)};}
#define printm(m) {for(auto &pa:m){cout << pa.first << "," << pa.second << " ";};cout<<endl;}
ll min(int a,ll b) { if (a<b) return a; return b; }
ll min(ll a,int b) { if (a<b) return a; return b; }
ll max(int a,ll b) { if (a>b) return a; return b; }
ll max(ll a,int b) { if (a>b) return a; return b; }
ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b, a%b); }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
string to_upper(string a) { for (ll i=0;i<(ll)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A'; return a; }
string to_lower(string a) { for (ll i=0;i<(ll)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A'; return a; }
bool is_prime(ll a)
{
if(a==1) return false;
for(ll i=2;i*i<=a;i++)
{
if (a%i==0) return false;
}
return true;
}
ll binpow(ll a, ll b, ll m)
{
a %= m;
ll res = 1;
while (b > 0)
{
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
ll moddiv(ll numerator,ll denominator, ll mod)
{
numerator %= mod;
denominator %= mod;
return numerator * binpow(denominator,mod-2,mod) % mod;
}
//DSU https://cp-algorithms.com/data_structures/disjoll_set_union.html
const ll DSUN = 0;
ll parent[DSUN];
ll set_size[DSUN];
ll find_set(ll v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void make_set(ll v) {
parent[v] = v;
set_size[v] = 1;
}
void union_sets(ll a, ll b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (set_size[a] < set_size[b])
swap(a, b);
parent[b] = a;
set_size[a] += set_size[b];
}
}
//DSU
//https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
vector<char> segmentedSieve(ll L, ll R) {
// generate all primes up to sqrt(R)
ll lim = sqrt(R);
vector<char> mark(lim + 1, false);
vector<ll> primes;
for (ll i = 2; i <= lim; ++i) {
if (!mark[i]) {
primes.emplace_back(i);
for (ll j = i * i; j <= lim; j += i)
mark[j] = true;
}
}
vector<char> isPrime(R - L + 1, true);
for (ll i : primes)
for (ll j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
isPrime[j - L] = false;
if (L == 1)
isPrime[0] = false;
return isPrime;
}
//segtree
vector<ll> builder(vector<ll> &arr)
{
//min
ll identityelement = LONG_LONG_MAX;
vector<ll> segtree;
ll n,segtree_size;
n=arr.size();
segtree_size=1;
while(segtree_size<n)
{
segtree_size<<=1;
}
segtree.assign(2*segtree_size,identityelement);
for(ll i=0;i<n;i++)
{
segtree[segtree_size+i]=arr[i];
}
for(ll i=segtree_size-1;i>0;i--)
{
segtree[i]=min(segtree[i*2],segtree[i*2+1]);
}
return segtree;
}
ll query(vector<ll>&segtree,vector<ll>&lazy,ll query_l,ll query_r,ll val,ll node_l,ll node_r,ll node)
{
// min
ll identity_element = INT_MAX;
if(lazy[node]!=0)
{
segtree[node]=lazy[node];
if(node_l!=node_r)
{
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
}
lazy[node]=0;
}
if(val!=-1 && query_l<=node_l && node_r<=query_r)
{
segtree[node]=val;
if(node_l!=node_r)
{
lazy[node*2]=val;
lazy[node*2+1]=val;
}
lazy[node]=0;
}
if(query_l<=node_l && node_r<=query_r)
{
return segtree[node];
}
else if(node_r<query_l || query_r<node_l)
{
return identity_element;
}
else
{
ll mid = node_l+(node_r-node_l)/2;
ll sum = min(query(segtree,lazy,query_l,query_r,val,node_l,mid,node*2),query(segtree,lazy,query_l,query_r,val,mid+1,node_r,node*2+1));
segtree[node] = min(segtree[node*2],segtree[node*2+1]);
return sum;
}
return 0ll;
}
//segtree
ll kadane(vll &a)
{
ll ans = a[0], sum = 0;
for (ll r = 0; r < a.size(); r++)
{
sum += a[r];
ans = max(ans, sum);
sum = max(sum, 0);
}
return ans;
}
vector<bool>sieve(ll n)
{
vector<bool>ret(n+1,true);
ret[0]=false;
ret[1]=false;
for(ll i=2;i<=n;i++)
{
if(ret[i])
{
for(ll j=i*i;j<=n;j+=i)
{
ret[j]=false;
}
}
}
return ret;
}
ll splitinv_count(vll &arr,ll l,ll r)
{
if(l==r)
return 0;
ll mid=l+(r-l)/2;
vll barr;
vll carr;
for(int i=l;i<=mid;i++)
barr.push_back(arr[i]);
for(int i=mid+1;i<=r;i++)
carr.push_back(arr[i]);
ll ans=0;
ll k=l;
int j=0;
for(int i=0;i<barr.size();i++)
{
while(j<carr.size()&&barr[i]>carr[j])
{
arr[k]=carr[j];
k+=1;
j+=1;
}
ans+=j;
arr[k]=barr[i];
k+=1;
}
while(j<carr.size())
{
arr[k]=carr[j];
k+=1;
j+=1;
}
return ans;
}
ll inversion_count(vll &arr,ll l,ll r)
{
if(l==r)
return 0;
ll mid=l+(r-l)/2;
ll x,y,z;
x=inversion_count(arr,l,mid);
y=inversion_count(arr,mid+1,r);
z=splitinv_count(arr,l,r);
return x+y+z;
}
bool ascdesc(const pll& a, const pll& b)
{
if (a.first != b.first)
return (a.first < b.first);
else
return (a.second > b.second);
}
bool comp(const pll& a, const pll& b)
{
if(a.first*a.second == b.first*b.second)
return (a.first < b.first);
else
return (a.first*a.second > b.first*b.second);
}
ll fracmod(ll a, ll b,ll m)
{
return ( (a % m) * ( binpow(b%m, m-2, m) % m) ) % m;
}
//https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
void constructLps(string &pat, vector<int> &lps) {
// len stores the length of longest prefix which
// is also a suffix for the previous index
int len = 0;
// lps[0] is always 0
lps[0] = 0;
int i = 1;
while (i < pat.length()) {
// If characters match, increment the size of lps
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
// If there is a mismatch
else {
if (len != 0) {
// Update len to the previous lps value
// to avoid reduntant comparisons
len = lps[len - 1];
}
else {
// If no matching prefix found, set lps[i] to 0
lps[i] = 0;
i++;
}
}
}
}
vector<int> search(string &pat, string &txt) {
int n = txt.length();
int m = pat.length();
vector<int> lps(m);
vector<int> res;
constructLps(pat, lps);
// Pointers i and j, for traversing
// the text and pattern
int i = 0;
int j = 0;
while (i < n) {
// If characters match, move both pointers forward
if (txt[i] == pat[j]) {
i++;
j++;
// If the entire pattern is matched
// store the start index in result
if (j == m) {
res.push_back(i - j);
// Use LPS of previous index to
// skip unnecessary comparisons
j = lps[j - 1];
}
}
// If there is a mismatch
else {
// Use lps value of previous index
// to avoid redundant comparisons
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return res;
}
ll solved[1048576];
ll rem[1048576];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
//vll segtree,lazy;
//ll segtree_size;
//segtree=builder(arr);
//segtree_size=segtree.size()/2;
//lazy.assign(segtree_size*2,0);
//update: query_sum(segtree,lazy,a,b,c,1,segtree_size,1);
//query: cout << query_sum(segtree,lazy,a,b,-1,1,segtree_size,1) << endl;
ll n,m,k;
cin >> n >> m;
vll arr(n);
vll barr(m);
for(int i=0;i<n;i++)
cin >> arr[i];
for(int i=0;i<m;i++)
cin >> barr[i];
ll limit=1<<m;
for(int i=0;i<limit;i++)
rem[i]=10000;
queue<ll> BFS;
unordered_set<ll>seen({0});
BFS.push(0);
rem[0]=arr[0];
while(!BFS.empty())
{
ll curr=BFS.front();
BFS.pop();
//cout << curr << " , " << rem[curr]<< endl;
for(int i=0;i<m;i++)
{
ll _solved=solved[curr];
ll _rem=rem[curr];
if((1<<i)&curr || barr[i]>_rem)
continue;
_rem-=barr[i];
if(_rem==0)
{
_solved+=1;
if(_solved==n)
{
cout << "YES\n";
return 0;
}
_rem=arr[_solved];
}
ll neighbour=curr|(1<<i);
if(seen.find(neighbour)==seen.end())
{
seen.insert(neighbour);
BFS.push(neighbour);
}
if(_solved>solved[neighbour] || _solved==solved[neighbour] && _rem<rem[neighbour])
{
solved[neighbour]=_solved;
rem[neighbour]=_rem;
}
}
}
cout << "NO\n";
}
| # | 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... |
