Submission #1196400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196400		easterp	Bank (IZhO14_bank)	C++20	0 / 100	0 ms	328 KiB

bank

///                SOURCE: EASTERP
///                    THPT TD

#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define pii pair<int, int>
#define pll pair<long, long>
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
#define forin(i, a) for(auto i : a)
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define pb push_back
#define eb emplace_back
#define el "\n"
#define fi first
#define se second
#define N 100006
#define MOD (int) 1000000007
#define EASTERP 0
#define EASTER 1

using ll = long long;
using namespace std;


/// KHAIBAO

int n, m;
vi a, b;
bool dp[1 << 20];
int salarySum[1 << 20];

///CODE NAO EASTERP

void Solve() {
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    FOR(i, 0, n - 1) cin >> a[i];
    FOR(i, 0, m - 1) cin >> b[i];

    
    sort(b.begin(), b.end(), greater<int>());

    int total_states = 1 << n;
    dp[0] = true;

    
    FOR(mask, 0, total_states - 1) {
        salarySum[mask] = 0;
        FOR(i, 0, n - 1) {
            if (mask & (1 << i))
                salarySum[mask] += a[i];
        }
    }

    FOR(mask, 0, total_states - 1) {
        if (!dp[mask]) continue;
        int usedSum = salarySum[mask];

        FOR(i, 0, n - 1) {
            if (!(mask & (1 << i))) { 
                int newMask = mask | (1 << i);
                int target = usedSum + a[i];

                
                int sum = 0;
                for (int j = 0; j < m; ++j) {
                    if (sum + b[j] <= target)
                        sum += b[j];
                    if (sum == target) break;
                }

                if (sum == target)
                    dp[newMask] = true;
            }
        }
    }
    if (dp[total_states - 1])
        cout << "YES";
    else
        cout << "NO";
}

int main(){

    fastIO;

   

    Solve();
    return 0;
}

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