Submission #638325

#TimeUsernameProblemLanguageResultExecution timeMemory
638325CookieBank (IZhO14_bank)C++14
100 / 100
106 ms8536 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...