Submission #869222

#	Time	Username	Problem	Language	Result	Execution time	Memory
869222		JakobZorz	Bank (IZhO14_bank)	C++17	100 / 100	102 ms	8688 KiB

bank

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second

//#define TEST_CASES

int n,m;
int pay[20];
int note[20];
int pre[1<<20];
int rem[1<<20];

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>pay[i];
    for(int i=0;i<m;i++)
        cin>>note[i];
    
    for(int mask=0;mask<(1<<m);mask++){
        for(int nnote=0;nnote<m;nnote++){
            int nmask=mask|(1<<nnote);
            if(nmask==mask)
                continue;
            
            int nrem=rem[mask]+note[nnote];
            int npre=pre[mask];
            if(nrem>pay[npre])
                continue;
            if(nrem==pay[npre]){
                nrem=0;
                npre++;
                if(npre==n){
                    cout<<"YES\n";
                    return;
                }
            }
            
            if(npre>=pre[nmask]){
                pre[nmask]=npre;
                rem[nmask]=nrem;
            }
        }
    }
    
    cout<<"NO\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);
    //freopen("bank.out","w",stdout);
#ifdef TEST_CASES
    int t;cin>>t;while(t--)solve();
#else
    solve();
#endif
    return 0;
}

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