Submission #998106

#	Time	Username	Problem	Language	Result	Execution time	Memory
998106		HUYHDUVE	Bank (IZhO14_bank)	C++14	100 / 100	119 ms	12888 KiB

bank

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

struct state{
    int id = -1, left = -1, cnt = -1;

    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(){
//    freopen("A.IN", "r", stdin);
//    freopen("A.OUT", "w", stdout);


    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){
                if(z.id < n) z.id ++;
                z.left = (z.id < n ? peo[z.id] : 0);

            }



            if(take[mask | (1 << j)] < z){
                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;
        }
    }

//    for(int mask = 0; mask < (1 << m); mask ++){
//        bitset<6> a(mask);
//        cout << a << ' ' << take[mask].id << ' ' << take[mask].left << "\n";
//    }



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

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