Submission #998093

#	Time	Username	Problem	Language	Result	Execution time	Memory
998093		HUYHDUVE	Bank (IZhO14_bank)	C++14	19 / 100	78 ms	12740 KiB

bank

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll const INF = 1e8;

struct state{
    int id = INF, left = INF, cnt = INF;

    bool operator < (const state &other){
        if(id == other.id){
            if(cnt == other.cnt) {
                return left < other.left;
            }
            return cnt < other.cnt;
        }
        return id < other.id;
    }
};



int main(){



    int n, m; cin >> n >> m;
    vector<int> peo(n), cash(m);
    for(auto &it : peo) cin >> it;
    for(auto &it : cash) cin >> it;

    sort(peo.rbegin(), peo.rend());
    sort(cash.rbegin(), cash.rend());

    vector<state> take(1 << m);
    take[0].id = 0;
    take[0].left = peo[0];
    take[0].cnt = 0;

    for(int mask = 0; mask < (1 << m); mask++){
        for(int j = 0; j < m; j++){
            if(mask & (1 << j)) continue;

            state z = take[mask];

            if(cash[j] <= z.left){
                z.left -= cash[j];
                z.cnt ++;
            }


            if(z.left == 0){
                z.id ++;
                z.left = (z.id < n ? peo[z.id] : 0);

            }



            if(z < take[mask | (1 << j)]){
                take[mask | (1 << j)] = z;
            }
        }
    }
    bool f = 0;
    for(int mask = 0; mask < (1 << m); mask ++){
        if(take[mask].id == n && take[mask].left == 0){
            f = 1;
        }
    }



    if(f) cout << "YES";
    else cout << "NO";
}

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