Submission #1001455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001455		anHiep	Bank (IZhO14_bank)	C++14	100 / 100	416 ms	32340 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define pb push_back
#define fi first
#define se second
 
const int oo = 1e18;
const int maxn = 1e5 + 10;
 
bool dp[23][1<<20];
int s[1<<20];
vector<int> f[23];
 
void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    for(int j = 0; j < (1<<m); j++){
        int sum = 0;
        for(int i = 0; i < m; i++){
            if(j&(1<<i)) sum+=b[i];
        }
        s[j] = sum;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (1<<m); j++){
            if(s[j] == a[i]){
                    f[i].pb(j);
            }
        }
    }
    memset(dp,0, sizeof(dp));
    dp[0][0] = 1;
    bool c = 0;
    long long pf = 0;
    for(int i = 1; i <= n; i++){
    	pf += a[i];
        for(int j = 0; j < (1<<m); j++){
        		if(s[j] != pf) continue;
                for(auto x: f[i]) if((x&j)==x)dp[i][j] |= dp[i - 1][j ^ x];
                if(i == n && dp[i][j]){
                    c = 1; break;
                }
        }
    }
    if(c) cout<<"YES";
    else cout<<"NO";
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    solve();
}

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