Submission #1306982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306982		ng.annhaat	Bank (IZhO14_bank)	C++20	100 / 100	136 ms	1616 KiB

bank

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░  ░░░░░░░░   ░░░░░   ░           ░   ░░░░   ░░░░░     ░░░░░░        ░░░░
▒▒▒▒▒▒  ▒  ▒▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒
▒▒▒▒▒  ▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒   ▒▒▒▒▒▒▒▒   ▒   ▒▒▒▒   ▒▒
▓▓▓▓   ▓▓▓   ▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓          ▓   ▓▓▓▓▓▓▓▓   ▓  ▓   ▓▓▓▓▓▓
▓▓▓       ▓   ▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓   ▓▓▓▓▓▓▓▓   ▓   ▓▓   ▓▓▓▓
▓▓   ▓▓▓▓▓▓▓   ▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓▓▓   ▓▓▓▓▓   ▓▓   ▓▓▓▓   ▓▓
█   █████████   ███      ████████   █████   ████   █████     ██████   ██████
███████████████████████████████████████████████████████████████████████████████

         ▄▄▄      ███▄    █  ███▄    █   ██░ ██  ▄▄▄      ▄▄▄     ▄▄▄█████▓
        ▒████▄    ██ ▀█   █  ██ ▀█   █ ▒▓██░ ██ ▒████▄   ▒████▄   ▓  ██▒ ▓▒
        ▒██  ▀█▄ ▓██  ▀█ ██▒▓██  ▀█ ██▒░▒██▀▀██ ▒██  ▀█▄ ▒██  ▀█▄ ▒ ▓██░ ▒░
        ░██▄▄▄▄██▓██▒  ▐▌██▒▓██▒  ▐▌██▒ ░▓█ ░██ ░██▄▄▄▄██░██▄▄▄▄██░ ▓██▓ ░
         ▓█   ▓██▒██░   ▓██░▒██░   ▓██░ ░▓█▒░██▓ ▓█   ▓██ ▓█   ▓██  ▒██▒ ░
         ▒▒   ▓▒█░ ▒░   ▒ ▒ ░ ▒░   ▒ ▒   ▒ ░░▒░▒ ▒▒   ▓▒█ ▒▒   ▓▒█  ▒ ░░
          ░   ▒▒ ░ ░░   ░ ▒░░ ░░   ░ ▒░  ▒ ░▒░ ░  ░   ▒▒   ░   ▒▒     ░
          ░   ▒     ░   ░ ░    ░   ░ ░   ░  ░░ ░  ░   ▒    ░   ▒    ░ ░
              ░           ░          ░   ░  ░  ░      ░        ░


*/
//#include <bits/BaoMinhTranc++.h>
#include <bits/stdc++.h>
#define int int64_t
//#define ll int64_t
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define ALLr(x) x.rbegin(),x.rend()
#define upgrade ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define name "youreagoodmanarthur"
using namespace std;
const int Max=1<<20;
const int N=23;
const int INF=1e18;
const int MOD=998244353;
const int MOD2=1e9+8;
const int base=26;
const int LOG=20;
template<class X,class Y>
    bool minimize(X& x,const Y& y)
    {
        if(x>y){
            x=y;
            return 1;
        }return 0;
    }
template<class X,class Y>
    bool maximize(X& x,const Y& y)
    {
        if(x<y){
            x=y;
            return 1;
        }return 0;
    }
int n,m;
int a[N],b[N];
bool dp[Max];
int show[20003];
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    for(int i=1;i<=n;i++)show[(a[i]+=a[i-1])]=i;
    for(int i=1;i<n*1000;i++)maximize(show[i],show[i-1]);
    dp[0]=1;
    bool ans=0;
    for(int mask=0;mask<(1<<m);mask++){
        if(dp[mask]){
            int s=0;
            for(int i=0;i<m;i++)if(mask>>i&1)s+=b[i];
            int pay=show[s];
            if(pay==n){
                ans=1;break;
            }
            for(int i=0;i<m;i++)if(!(mask>>i&1))if(s+b[i]<=a[pay+1])dp[mask^(1<<i)]=1;
        }
    }
    if(ans)cout<<"YES";
    else cout<<"NO";
}
void prepare()
{

}
signed main()
{
    upgrade
    if(fopen(name".INP","r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }
    prepare();
    int test=1;
//    cin>>test;
    while(test--)solve();
    return 0;
}
/*

                                                                                                       ░▓▓
                                                                 ░▒▒▒         ░▒▒▒▒▒▒░░░               ░▓▓
▓▒        ▒▓▓▓▓▓▓▓▓▓▓▓▓▒                  ░▓▓▓▓▓▓▓▓▓▓▓▒░       ▒▓▓▒      ▒▒▒▒░   ░░░░▒░▒▒▒▒▒▒          ░▓▓    ░░▒▒▒▒▒░░
▒▓▓▒   ▒▓▓░            ░▓▓▒           ░▓▓▓▒            ░▒▓▓░░▓▓▒      ▒▒▒  ▒▒▒▒▒▒░░░▒▒▒▒▒▒▒▒▒▒▒░       ░▓▓▓▒▒▒▒▒▒▒▒▒▒▓▒▒░
   ▓▓▓▓▒                 ░▓▓▒       ▒▓▓▒                 ░▓▓▓░      ░▒░        ░▒▒▒▒▒▒▒▒  ▒▒▒░ ▒▒▒     ░▓▓
                          ░▓▓░     ▓▓▓                                                 ░▒▒▒ ▒▒▒ ░▒▒    ▒▓▒
                           ▒▓▒    ▓▓▓                                      ░░            ▒▒░ ▒▒▒ ▒▒░   ▓▓▓
                           ░▓▒   ░▓▓▓                                  ░▒  ▒▒░           ▒▒░ ▒▒░ ▒▒▒   ▓▓▓░
                           ░▓▒   ░▓▓▓▒                                 ▒▒▒ ░▒▒▒░       ░▒▒░ ░▒▒ ▒▒▒    ▓▓▓▒
                           ▒▓▒     ▓▓▓░                      ░      ▒▒░  ▒▒▒   ▒▒▒▒▒▒▒▒░  ▒▒▒▒▒▒▒▒     ░▓▓▓
                          ░▓▓▒      ▒▓▓▓▒                 ░▓▓▓▓▒     ░▒▒   ░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░ ▒▒▒░        ░▓▓▓
                           ░▒         ░▓▓▓▓▓▓▒░       ▒▓▓▓▓▓▒▓▓▒        ▒▒▒▒▒▒▒░    ░▒▒▒▒▒▒▒░             ▓▓▓▓▒▒       ▒▓▓▓▓
                                           ░░▓▓▓▓▓▓▓▓▒░░     ▒▓▒                 ░▒▒▒▒░                       ░▒▓▓▓▓▓▓▓▓▒░
                                                             ▒▓▓░                  ▒▒░
                            ▓▒                               ▒▓▓░                  ▒▒▒░
                            ▓▓▒                             ░▓▓▒                  ░▒▒▒▒
                             ▓▓▓░                          ▒▓▓▓                    ░▒▒▒
                               ░▓▓▓▓░                   ░▓▓▓▒
                                   ░▓▓▓▓▓▒▒░░░  ░░░▒▒▓▓▓▓░
                                         ░▒▒▒▒▒▒▒▒░
*/

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bank.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29