# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1208546 | raymoo_ | Bank (IZhO14_bank) | C++20 | 113 ms | 16852 KiB |
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define umap unordered_map
#define prq priority_queue
#define vect vector
#define rs resize
#define bend(v) v.begin(),v.end()
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
#define pii pair<int,int>
#define nextl cout << '\n'
#define el '\n'
#define deb cout<<"\nok\n";return
#define ll long long
#define int long long
#define dbl long double
#define popcnt __builtin_popcount
#define ctz __builtin_ctz
const ll INF=902337203695775807, N=2e5+69, MOD=1e9+7;
void ffopen(const string& file){
if(file.empty())return;
FILE *File = fopen((file+".inp").c_str(), "r");
if (File == NULL)return;
freopen((file + ".inp").c_str(), "r", stdin);
freopen((file + ".out").c_str(), "w", stdout);
}
int pm(int a,const int b=1e9+7){return ((a%b)+b)%b;}
int sq(int x){return x*x;}
ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){
if(a == -1 || b == -1)return -1;
ll g = __gcd(a,b);
if(b/g > lim/a)return -1;
return (a/g)*b;
}
int dp[1<<20][2];
void sol(){
int n, m;
cin >> n >> m;
int a[n], b[m];
for(int& i : a)cin >> i;
for(int& i : b)cin >> i;
memset(dp, -5, sizeof dp);
dp[0][0] = dp[0][1] = 0;
for(int mask=0;1<<m >mask;mask++){
for(int i=0;m>i;i++){
if(!(mask&(1<<i)))continue;
int pmask = mask ^ (1<<i);
if(dp[pmask][0] < 0)continue;
int x = a[dp[pmask][0]];
if(x == dp[pmask][1] + b[i]){
dp[mask][0] = max(dp[mask][0], dp[pmask][0]+1);
dp[mask][1] = 0;
}else if(x > dp[pmask][1] + b[i]){
dp[mask][0] = dp[pmask][0];
dp[mask][1] = dp[pmask][1] + b[i];
}
}
if(dp[mask][0] == n){
cout << "YES";
return ;
}
}cout << "NO";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ffopen("");
int t=1;
//cin >> t;
while(t--)sol();
}
/*
...-%%%%%%%%%%%...
.:**#%=%%%%%+........-%%%%. .
.%%%%%%=-..%#. .#%%.
%%%+.. .: *%%.
.%%. :. :%%%%%:.
.%%. ... .: :: .=%%%.
..%%. #%#:%. : :.. =%%.
%%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%..
.%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%.
.%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%.
=%%%...-%%%:::*%********%:::%%%****%::::::::%% .%-
.%::::%%***%=:%%**********%%********%:::::::=%-:. .%..
#%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%.
.%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%.
.%%#%+%%***************##*+=+*==********************%%.:. .%%
.%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%.
.#%#*********************%%**************++************%%::::::%* .%%%.
.%%***************#*****%%%****************************%%::::::%% .-%%%.
.#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%.
.%%**************#**%%%----%********%%**************#***#%%%#**%#******%*
.%%**************#%%%--.....%%*******%%**************#**********#%******%%.
.%%*************%%...........%%******%-%*************#***********%%*****%%.
.%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%#
.%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%%
.#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%.
.%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%.
.+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%-
..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%.
.%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%.
.%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%.
.%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%.
..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%.
.%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%.
..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%..
-%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%.
.%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%.
.%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%.
.+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%:
=%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%%
.%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%%
*%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%%
.%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%*
%%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%.
%%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%.
.%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%..
:%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% .
*%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*..
.%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . .....
%%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%.
..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%#
.-%%+. ... .%%%%%%%:.
*/
Compilation message (stderr)
# | 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... |