Submission #638325

#	Time	Username	Problem	Language	Result	Execution time	Memory
638325		Cookie	Bank (IZhO14_bank)	C++14	100 / 100	106 ms	8536 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#include<fstream>
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#define pii pair<int, int>
#define pll pair<ll, ll>
const ll mod = 1e9 + 7;
#include<fstream>
ifstream fin("guard.in");
ofstream fout("guard.out");
const int mxn = 5e4;
int n, m;
int a[21], b[21];
int mx[(1 << 20)], lft[(1 << 20)];
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 0, n)cin >> a[i];
    forr(i, 0, m)cin >> b[i];
    memset(mx, -1, sizeof(mx)); memset(lft, -1, sizeof(lft)); 
    mx[0] = lft[0] = 0;
    for(int i = 1; i < (1 << m); i++){
        for(int j = 0; j < m; j++){
            if(!(i & (1 << j)))continue;
            int old = i ^ (1 << j);
            if(mx[old] == -1)continue;
            int have = lft[old] + b[j];
            if(have < a[mx[old]]){
                if(mx[old] > mx[i]){
                    mx[i] = mx[old]; lft[i] = have;
                }
            }else if(have == a[mx[old]]){
                mx[i] = max(mx[i], mx[old] + 1);
                lft[i] = 0;
            }
            if(mx[i] == n){
               
                cout << "YES";
                return(0);
            }
        }
        
    }
    cout << "NO";
   
    return 0;
}

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