Submission #1183285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183285		faqinyeager	Bank (IZhO14_bank)	C++20	100 / 100	131 ms	78692 KiB

bank

#include <bits/stdc++.h>
#define ll unsigned long long
#define pii pair<ll, ll>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define ub(c, x) distance((c).begin(),lower_bound(c.begin(),c.end(), (x)))
#define ff first
#define ss second
#define N 200015
using namespace std;

const int inf = 1e9;

ll gcd(ll a, ll b){
    if(b == 0) return 1;
    return gcd(b, a % b);
}

const ll INF = 1e18;
vector<vector<pair<ll,ll>>> g;
ll n, m, x;

vector<ll> djikstras(ll s, ll n){
    vector<ll> dist(n, INF);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll,ll>>> pq;
    vector<bool> vist(n, false);
    dist[s] = 0;
    pq.push({dist[s], s});
    
    while(!pq.empty()){
        ll a = pq.top().second; 
        pq.pop();
        if(vist[a]) continue;
        vist[a] = true;
        for(auto [b , w]: g[a]){
            if(dist[a] + w < dist[b]){
                dist[b] = dist[a] + w;
                pq.push({dist[b], b});
            }
        }
    }
    return dist;
}

pair<ll, ll> dp[5000000];

void F(){
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    
    memset(dp, -1, sizeof dp);
    dp[0] = {0, 0};
    
    for(ll i = 0; i < n; i++) cin >> a[i];
    for(ll j = 0; j < m; j++) cin >> b[j];
    
    for(ll mask = 0; mask < (1 << m); mask++){
        for(ll last = 0; last < m; last++){
            if(!(mask & (1 << last))) continue;
            ll pre = mask ^ (1 << last);
            if(dp[pre].ff == -1) continue;
            
            ll rem = dp[pre].ss + b[last];
            ll need = a[dp[pre].ff];
            
            if(rem < need) dp[mask] = {dp[pre].ff, rem};
            if(rem == need) dp[mask] = {dp[pre].ff + 1, 0};
        }
        if(dp[mask].ff == n){
            cout << "YES"; return;
        }
    }
    cout << "NO";
}

int main() {
    int tc = 1;
    //cin >> tc;
    while(tc--) F();
}

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