Submission #572518

#	Time	Username	Problem	Language	Result	Execution time	Memory
572518		Dan4Life	Bank (IZhO14_bank)	C++17	100 / 100	164 ms	16832 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll // delete if causing problems
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define mod(a) (a+MOD)%MOD
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()

const int maxn = (int)2e5+10; // change when needed!
const int MOD = (int)1e9+7; // same!
const int INF = (int)2e9;
const ll LINF = (ll)4e18;
int n, m, x, y, l, r, k, q, t;
map<int, int> M, N;
pair<int,int> dp[1<<21];
int a[21], b[21];
void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    dp[0] = {0,0};
    for(int i = 0; i < (1<<m); i++){
        for(int j = 0; j < m; j++){
            if(i&(1<<j)) continue;
            int n_i = i|(1<<j);
            int tot = dp[i].se+b[j];
            if(tot<a[dp[i].fi])
                dp[n_i] = max(dp[n_i], {dp[i].fi, dp[i].se+b[j]});
            else if(tot==a[dp[i].fi])
                dp[n_i] = max(dp[n_i], {dp[i].fi+1, 0});
        }
        if(dp[i].fi==n){cout<<"YES";return;}
    }
    cout << "NO";
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
}

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