제출 #897243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897243		asdasdqwer	은행 (IZhO14_bank)	C++14	100 / 100	118 ms	8788 KiB

bank

#pragma GCC optimize("O3")
// #pragma GCC target("avx,avx2,sse4")
    
#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n,m;cin>>n>>m;
    vector<int> a(n);
    for (int &x:a)cin>>x;
    vector<int> b(m);
    for (int &y:b)cin>>y;

    vector<int> covered(1<<m,0), leftover(1<<m, 0);
    
    for (int s=1;s<(1<<m);s++) {
        int cp=s;
        int cnt=0;

        while (cp) {
            if ((cp&1)==1) {
                int pv=s ^ (1<<cnt);

                if (covered[pv] == n) {
                    covered[s]=n;
                    leftover[s]=0;
                }

                else {
                    int amount = leftover[pv] + b[cnt];

                    int fnd = a[covered[pv]];

                    if (amount == fnd && covered[pv] + 1 > covered[s]) {
                        covered[s] = covered[pv]+1;
                        leftover[s] = 0;
                    }

                    else if (amount < fnd && covered[pv] >= covered[s]) {
                        covered[s] = covered[pv];
                        leftover[s] = amount;
                    }
                }
            }

            cp>>=1;
            cnt++;
        }

        // cout<<covered[s]<<" "<<s<<"\n";
    }

    if (covered.back() == n) {
        cout<<"YES\n";
    }

    else {
        // cout<<covered.back()<<"\n";
        cout<<"NO\n";
    }
}

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