Submission #1164413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164413		ivaziva	Bank (IZhO14_bank)	C++17	100 / 100	98 ms	8644 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#define MAXN 20

int n,m;
int a[MAXN],b[MAXN];
int dp[1<<MAXN],dp1[1<<MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=0;i<n;i++) cin>>a[i];
    for (int i=0;i<m;i++) cin>>b[i];
    dp[0]=dp1[0]=0;
    for (int maska=1;maska<(1<<m);maska++) {dp[maska]=-1;dp1[maska]=-1;}
    for (int maska=1;maska<(1<<m);maska++)
    {
        for (int bit=0;bit<m;bit++)
        {
            if ((maska&(1<<bit))==0) continue;
            if (dp[maska^(1<<bit)]==-1) continue;
            int target=a[dp[maska^(1<<bit)]],left=dp1[maska^(1<<bit)]+b[bit];
            if (left<target) {dp[maska]=dp[maska^(1<<bit)];dp1[maska]=left;}
            else if (left==target) {dp[maska]=dp[maska^(1<<bit)]+1;dp1[maska]=0;}
        }
        if (dp[maska]==n) {cout<<"YES"<<endl;return 0;}
    }
    cout<<"NO"<<endl;return 0;
}

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