Submission #765751

#	Time	Username	Problem	Language	Result	Execution time	Memory
765751		tinhngoVN	Bank (IZhO14_bank)	C++14	100 / 100	106 ms	33228 KiB

bank

#include <bits/stdc++.h>

#define MAXN 22

using namespace std;


int n,m,a[MAXN], b[MAXN];
int amt[1<<MAXN] , cnta[1<<MAXN];
//amt[i] la so tien con lai khi tra luong cho mot so nguoi o trang thai nhung to tien la i
//cnta[i] la so nguoi duoc tra luong o trang thai nhung to tien la i

void inp()
{
    cin>>n>>m;
    for (int i=0; i<n; ++i) cin>>a[i];
    for (int i=0; i<m; ++i) cin>>b[i];
}
void out()
{
    memset(amt , -1 , sizeof(amt));
    memset(cnta , -1 , sizeof(cnta));
    amt[0]=0; cnta[0]=0;
    for (int mask=0; mask<(1<<m); ++mask)
    {
        for (int i=0; i<m; ++i)
        {
            if ((mask&(1<<i))>0)
            {
                int pre_mask = mask & ~(1<<i);
                if(cnta[pre_mask] == -1) continue; //Neu so nguoi o trang thai truoc chua duoc tinh
                int new_amt = amt[pre_mask] + b[i];
                int cur = a[cnta[pre_mask]];
                if(new_amt < cur)
                {
                    cnta[mask] = cnta[pre_mask];
                    amt[mask] = new_amt;
                }
                else if (new_amt==cur)
                {
                    cnta[mask] = cnta[pre_mask]+1;
                    amt[mask] = 0;
                }
            }
        }
        if(cnta[mask] == n)
        {
            cout<<"YES\n";
            return ;
        }
    }
    cout<<"NO\n";
}

int main()
{
    inp();
    out();
}

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