제출 #1303777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303777		vladneagu	은행 (IZhO14_bank)	C++20	71 / 100	1095 ms	13284 KiB

bank

#include <iostream>
#include <map>
#include <algorithm>
#include <set>
#include <vector>
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
const int maxn=21;
int n,m;
int vals[maxn];
map<int,vector<int>> fv;
bool fvv[1005];
int coins[maxn];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>vals[i];
        fvv[vals[i]]=1;
    }
    for (int i=0;i<m;i++) {
        cin>>coins[i];
    }
    for (int mask=0;mask<(1<<m);mask++) {
        int sum=0;
        for (int i=0;i<m;i++) {
            if (mask&(1<<i)) {
                sum+=coins[i];
            }
        }
        if (fvv[sum]==1) {
            fv[sum].push_back(mask);
        }
    }
    set<int> s(fv[vals[1]].begin(),fv[vals[1]].end());
    for (int i=2;i<=n;i++) {
        set<int> s2;
        if (s.size()==0)break;
        for (auto it:fv[vals[i]]) {
            for (auto it2:s) {
                if ((it&it2)==0)s2.insert(it|it2);
            }
        }
        s.swap(s2);
    }
    if (s.size()) {
        cout<<"YES";
    }else cout<<"NO";
    return 0;
}

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