Submission #673347

#	Time	Username	Problem	Language	Result	Execution time	Memory
673347		beedle	Bank (IZhO14_bank)	C++17	100 / 100	163 ms	16844 KiB

bank

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <complex>
#include <assert.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define ld long long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 1000000007ll
#define INF 1e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

signed main()
{
    fast;

    // freopen("bank.in","r",stdin);
    // freopen("bank.out","w",stdout);

    ll n,m;
    cin>>n>>m;
    ll p[n], notes[m];
    rep(i,0,n-1)
    cin>>p[i];
    rep(i,0,m-1)
    cin>>notes[i];

    vector <ll> cancover(1<<m,-1);
    vector <ll> left(1<<m);

    rep(mask,0,(1<<m)-1)
    rep(idx,0,m-1)
    if(mask&(1ll<<idx))
    left[mask]+=notes[idx];

    rep(mask,1,(1<<m)-1)
    {
        rep(idx,0,m-1)
        if(mask&(1ll<<idx))
        {
            ll submask=mask^(1ll<<idx);
            ll next=cancover[submask]+1;
            if(next==n)
            {
                cancover[mask]=n-1;
                left[mask]=left[submask]+notes[idx];
            }
            else
            {
                if(left[submask]==p[next] || left[submask]+notes[idx]==p[next] || notes[idx]==p[next])
                {
                    if(next>cancover[mask])
                    {
                        cancover[mask]=next;
                        left[mask]=left[submask]+notes[idx]-p[next];
                    }
                }
                else
                {
                    if(cancover[submask]>cancover[mask])
                    {
                        cancover[mask]=cancover[submask];
                        left[mask]=left[submask]+notes[idx];
                    }
                }
            }
        }
    }

    bool ans=false;
    rep(i,0,(1<<m)-1)
    ans|=(cancover[i]==n-1);

    // cout<<cancover[20]<<" "<<left[20]<<endl;
    // cout<<cancover[21]<<" "<<left[21]<<endl;

    cout<<(ans?"YES":"NO");

    return 0;  
}

/*
1 5
8 
4 2 5 1 3
*/

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