제출 #1324264

#제출 시각아이디문제언어결과실행 시간메모리
1324264paskalisapo은행 (IZhO14_bank)C++20
100 / 100
103 ms8612 KiB
#include<bits/stdc++.h>
using namespace std;

int main( ){
    int n ,m ;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0;i < n ;i++){
        cin >> a[i];
    }
    for(int i = 0;i < m ;i++) {
        cin >> b[i];
    }
    // max prefix i can pay for a mask
    vector<int> maxpref((1 << m), -1);

    // the sum of money left for a mask after paying the max prefix
    vector<int> leftover((1 << m), -1);
    maxpref[0] = 0;
    leftover[0] = 0;
    bool valid = false;
    for(int mask = 0;mask < (1 << m) ;mask++){
        if(maxpref[mask] == -1){ 
            continue;
        }
        if(maxpref[mask] == n) {
            valid = true;
            break;
        }
        for(int bit = 0; bit < m; bit++)  {
            // can not be a new bit since it is already in the mask
            if((1 << bit) & mask) {
                continue;
            }

            //already full or invalid sequence so don't care
            if(maxpref[mask] == n ||leftover[mask] + b[bit] > a[maxpref[mask]]) {
                continue;
            }
            
            // add leftover
            if(leftover[mask] + b[bit] < a[maxpref[mask]]) {
                maxpref[mask | (1 << bit)] = maxpref[mask];
                leftover[mask | (1 << bit)] = leftover[mask] + b[bit];
            }
            // pay another person
            else {
                maxpref[mask | (1 << bit)] = maxpref[mask] + 1;
                leftover[mask | (1 << bit)] = 0;
            }
        }   
    }

    if(valid){
        cout <<"YES" << endl;
    }

    else {
        cout << "NO" << endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...