제출 #1165922

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165922		lidplf	은행 (IZhO14_bank)	C++20	52 / 100	1095 ms	12872 KiB

bank

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define MOD2 998244353
using namespace std;
void solve(int cas){ 
    int n,m; cin>>n>>m;
    vector<ll> people(n), bank(m);
    for (auto& a: people) cin>>a;
    for (auto& a: bank) cin>>a;
    vector<vector<ll>> sm(1001);
    for (int i = 1; i < (1<<m); i++){
        ll s = 0;
        for (int j = 0; j < m; j++){
            if ((i>>j)&1) s+=bank[j];
        }
        if (s <= 1000)
            sm[s].emplace_back(i);
    }
    vector<vector<bool>> dp(n+1, vector<bool> (1<<m));
    for (int i = 0; i < (1<<m); i++) dp[n][i] = true;
    for (int i = n - 1; i >= 0; i--){
        for (int mask = 0; mask < (1<<m); mask++){
            for (ll m1: sm[people[i]]){
                if ((m1&mask)==0){
                    dp[i][mask] = (dp[i][mask] || dp[i+1][mask|m1]);
                }
            }
        }
    }
    cout << (dp[0][0] ? "YES" : "NO") << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    //cin>>t;
    for (int i = 1; i <= t; i++){
        solve(i);
    }
    return 0;
}

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