제출 #1326270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326270		zhoyanov	은행 (IZhO14_bank)	C++20	100 / 100	106 ms	16836 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
#define Edge "Edige"
#define all(x) x.begin(),x.end()
#define ssd ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e6+5,N=30,mod = 1e9+7,INF=1e15,prime=67;
pair<int,int> dp[maxn];
void solve(){
    int n,m;
    cin >>n>>m;
    int a[n+5];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int b[m+5];
    for(int i=0;i<m;i++){
        cin >> b[i];
    }
    for(int i=1;i<(1<<m);i++)dp[i].F=-1,dp[i].S=-1;
    for(int mask=0;mask<(1<<m);mask++){
        for(int i=0;i<m;i++){
            if((mask & (1<<i)) || dp[mask].F==-1 || dp[mask].F==n)continue;
            int nm = mask | (1<<i);
            pair<int,int> st;
            if(dp[mask].S+b[i]>a[dp[mask].F])continue;
            if(dp[mask].S+b[i]<a[dp[mask].F])st = {dp[mask].F,dp[mask].S+b[i]};
            else st = {dp[mask].F+1,0ll};
            dp[nm] = max(dp[nm],st);
        }
    }
    for(int i=0;i<(1<<m);i++){
        if(dp[i].F==n){
            cout<<"YES\n";return;
        }
    }
    cout<<"NO\n";
}
signed main(){
//    freopen("cardgame.in","r", stdin);
//    freopen("cardgame.out","w", stdout);
    ssd
    int t=1;
//    cin>>t;
    for(int i=1;i<=t;i++){
//        cout<<"Case "<<i<<":"<<' ';
        solve();
    }
}

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