Submission #456411

#	Time	Username	Problem	Language	Result	Execution time	Memory
456411		ak2006	Bank (IZhO14_bank)	C++14	100 / 100	149 ms	8644 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int n,m;
    cin>>n>>m;
    
    int maxSet = (1<<m);
    
    vi leftOver(maxSet);
    vi numFilled(maxSet,-1);
    vi a(n + 1),b(m);

    for (int i = 1;i<=n;i++)cin>>a[i];
    for (int i = 0;i<m;i++)cin>>b[i];


    numFilled[0] = 0;
    leftOver[0] = 0;

    for (int mask = 0;mask < maxSet;mask++){
        for (int i = 0;i<m;i++){
            if (mask & (1<<i)){
                int prevMask = mask - (1<<i);

                if (numFilled[prevMask] == -1)continue;

                //if (mask == 5)cout<<leftOver[prevMask]<<" "<<b[i]<<endl;
                
                if (leftOver[prevMask] + b[i] < a[numFilled[prevMask] + 1]){
                    numFilled[mask] = numFilled[prevMask];
                    leftOver[mask] = leftOver[prevMask] + b[i];
                }

                else if (leftOver[prevMask] + b[i] == a[numFilled[prevMask] + 1]){
                    numFilled[mask] = numFilled[prevMask] + 1;
                    leftOver[mask] = 0;
                }
            }
            if (numFilled[mask] == n){cout<<"YES";return 0;}
        }
    }
    //cout<<numFilled[maxSet - 1]<<endl;
    if (numFilled[maxSet - 1] == n)cout<<"YES";
    else cout<<"NO";
    return 0;
}

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