Submission #888421

#	Time	Username	Problem	Language	Result	Execution time	Memory
888421		Mighilon	Bank (IZhO14_bank)	C++17	100 / 100	107 ms	8792 KiB

bank

#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "0" : "1");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto i: x) cerr << (f++ ? "\n" : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)

// #define cin fin
// #define cout fout
// const string FILE_NAME = "bank";
// ifstream fin(FILE_NAME + ".in");
// ofstream fout(FILE_NAME + ".out");
#endif

#define f first
#define s second
#define nl '\n'
typedef long long ll;
const int mxN = 5e3;
const int MOD = 1e9 + 7;



void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int j = 0; j < m; ++j)
        cin >> b[j];
    
    dbg(n, m, a, b)
    vector<int> people_covered(1 << m, -1), leftover(1 << m, -1);
    people_covered[0] = 0;
    leftover[0] = 0;
    for(int mask = 0; mask < 1 << m; ++mask){
        for(int i = 0; i < m; ++i){
            if((mask & (1 << i)) == 0) continue;
            int prev = mask & ~(1 << i);
            if(people_covered[prev] == -1) continue;
             
            int cur_sum = leftover[prev] + b[i];
            int target = a[people_covered[prev]];
            if(cur_sum < target){
                leftover[mask] = cur_sum;
                people_covered[mask] = people_covered[prev];
            }
            else if(cur_sum == target){
                leftover[mask] = 0;
                people_covered[mask] = people_covered[prev] + 1;
            }
        }
        if(people_covered[mask] == n){
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

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