제출 #1133233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133233		sitingfake	은행 (IZhO14_bank)	C++20	71 / 100	1095 ms	5576 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) ((x>>(i))&1)
#define off(x,i) (x^(1<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
const int mod=1e9+7;
const long long linf=1e18+3;
const int inf=1e9;
const int maxarr=1e6+5;
const double pi=acos(-1);
const int dx[]={0,1,-1,0};
const int dy[]={1,0,0,-1};
int n,m;
int a[22],b[22];
namespace sub3
{
    bool dp[1<<20][21];
    int val[1<<20];
    void init()
    {
        for(int mask=1;mask<(1<<m);mask++)
        {
            int tmp=0;
            for(int i=0;i<m;i++)
            {
                if(bit(mask,i))
                    tmp+=b[i+1];
            }
            val[mask]=tmp;
        }
    }
    void solve()
    {
        init();
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int mask=1;mask<(1<<m);mask++)
            {
                for(int sub=mask;1;sub=(sub-1)&mask)
                {
                    if(val[sub]==a[i])
                    {
                        dp[mask][i]|=dp[mask^sub][i-1];
                    }
                    if(sub==0) break;
                }
            }
        }
        for(int mask=1;mask<(1<<m);mask++)
            if(dp[mask][n])
            {
                cout<<"YES";
                return;
            }
        cout<<"NO";
    }
}
namespace sub1
{
    void solve()
    {
        for(int mask=1;mask<(1<<m);mask++)
        {
            int tmp=0;
            for(int i=0;i<m;i++)if(bit(mask,i)) tmp+=b[i+1];
            if(tmp==a[1])
            {
                cout<<"YES";
                return;
            }
        }
        cout<<"NO";
    }
}
namespace sub4
{
    bool dp[1<<20];
    int val[1<<20],pre[22];
    void init()
    {
        for(int mask=1;mask<(1<<m);mask++)
        {
            int tmp=0;
            for(int i=0;i<m;i++)
            {
                if(bit(mask,i))
                    tmp+=b[i+1];
            }
            val[mask]=tmp;
        }
        for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];

    }
    void solve()
    {
        init();
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int mask=1;mask<(1<<m);mask++)
            {
                for(int j=0;j<m;j++)
                {
                    if(bit(mask,j))
                    {
                        dp[mask]|=dp[off(mask,j)];
                    }
                }
            }
            for(int mask=0;mask<(1<<m);mask++) if(val[mask]!=pre[i])dp[mask]=0;
        }
        for(int mask=1;mask<(1<<m);mask++)
            if(dp[mask])
            {
                cout<<"YES";
                return;
            }
        cout<<"NO";
    }
}
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   cin>>n>>m;
   for(int i=1;i<=n;i++) cin>>a[i];
   for(int i=1;i<=m;i++) cin>>b[i];
   if(n==1) sub1::solve();
   else if(m<=14) sub3::solve();
   else sub4::solve();
   //execute;
}

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