제출 #1361342

#제출 시각아이디문제언어결과실행 시간메모리
1361342vlad7654은행 (IZhO14_bank)C++20
100 / 100
75 ms16828 KiB
#include <bits/stdc++.h>
using namespace std;
ifstream fin("bank.in");
ofstream fout("bank.out");
vector<int> a, b;
vector<pair<int,int> > dp;
int main() {
    int n, m;
    cin>>n>>m;
    a.resize(n+1);
    b.resize(m+1);
    dp.resize(1<<(m+1), {-1, -1});
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for (int i=1;i<=m;i++) {
        cin>>b[i];
    }
    auto build=[&]() {
        dp[0]={0, 0};
        for (int mask=0;mask<(1<<m);mask++) {
            for (int tip=1;tip<=m;tip++) {
                if (1<<(tip-1)&mask) continue;
                if (dp[mask].first==-1) continue;

                int old_val=dp[mask].second, old_prefix=dp[mask].first, new_val=b[tip], new_mask=1<<(tip-1)|mask;

                if (old_val+new_val<a[old_prefix+1]) {
                    dp[new_mask].first=old_prefix;
                    dp[new_mask].second=old_val+new_val;
                }
                if (old_val+new_val==a[old_prefix+1]) {
                    dp[new_mask].first=old_prefix+1;
                    dp[new_mask].second=0;
                }
            }
        }
    };
    build();
    for (int mask=0;mask<=(1<<m);mask++) {
        if (dp[mask].first==n) {
            cout<<"YES";
            return 0;
        }
    }
    cout<<"NO";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…