Submission #1236135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236135		SSSM	Bank (IZhO14_bank)	C++20	100 / 100	137 ms	8604 KiB

bank

#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"; 
}

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