제출 #1236135

#제출 시각아이디문제언어결과실행 시간메모리
1236135SSSM은행 (IZhO14_bank)C++20
100 / 100
137 ms8604 KiB
#include <bits/stdc++.h>

using namespace std;

#define SZ(a) (ll)a.size()
#define md(a) (a%mod+mod)%mod
#define F first
#define S second
#define pb push_pack
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll const maxn=1e6+10, mod=1e9+7, LOG=20, INF=1e18;

ll poww(ll a, ll b, ll MOD){
    if(b==0) return 1;
    return poww(a*a%MOD, b/2, MOD)*((b&1)?a:1)%MOD;
}

ll n, m, A[maxn], B[maxn], ps[maxn], dp[(1ll<<20)];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(ll i=0;i<n;i++) {
        cin>>ps[i];
        if(i>0) ps[i]+=ps[i-1];
    }
    for(ll i=0;i<m;i++) cin>>B[i];

    for(ll msk=0;msk<(1ll<<m);msk++)
    {
        ll s=0;
        for(ll i=0;i<m;i++) if(msk&(1ll<<i)) s+=B[i];
        for(ll i=0;i<m;i++) if(msk&(1ll<<i)){
            dp[msk]=max(dp[msk], dp[msk^(1ll<<i)]+(ps[dp[msk^(1ll<<i)]]==s));
        }
    }
    if(dp[(1ll<<m)-1]==n) cout<<"YES\n";
    else cout<<"NO\n"; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...