Submission #575844

#	Time	Username	Problem	Language	Result	Execution time	Memory
575844		LunaMeme	Bank (IZhO14_bank)	C++14	100 / 100	109 ms	8504 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
const int MAXN = 21;
ii dp[1 << MAXN]; // num of covered & left over
int main(){
    int n, m;
    cin >> n >> m;
    vi a(n), b(m);
    FOR(i, 0, n){
        cin >> a[i];
    }
    FOR(i, 0, m){
        cin >> b[i];
    }
    sort(a.rbegin(), a.rend());
    dp[0] = MP(0, 0);
    FOR(s, 1, 1 << m){
        dp[s] = MP(0, 0);
        FOR(i, 0, m){
            if ((s & (1 << i))== 0){
                continue;
            }
            int prev = s- (1 << i);
            int indx = dp[prev].first;
            int left = dp[prev].second;
            if (left + b[i] == a[indx]){
                left = 0;
                indx ++;
            }
            else if (b[i] == a[indx]){
                indx ++;
            }
            else{
                left += b[i];
            }
            dp[s] = max(dp[s], MP(indx, left));

        }
        if (dp[s].first == n){
            cout << "YES\n";
            return 0;
        }
        //cout << s << " : " << dp[s].first << ' ' << dp[s].second << '\n';
    }
    cout << "NO\n";

}

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