Submission #1232041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232041		rana_azka	은행 (IZhO14_bank)	C++20	71 / 100	1098 ms	47224 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 20;

int n, m, k;
int a[MAXN+5];
int b[MAXN+5];
int prefix[MAXN+5];
int dp[MAXN+5][2000000];
vector<int> v[MAXN+5];
int sum_bitmask[2000000+5];

void mulaidarinol(){}

void solve(){
	cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];

    for(int j = 0; j <= (1 << m); j++){
        for(int k = 0; k < m; k++){
            if((j >> k) & 1){
                sum_bitmask[j] += b[m-k];
            }
        }
    }

    for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + a[i];
    
    for(int j = 0; j <= (1 << m); j++) dp[0][j] = 1;
	
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= (1 << m); j++){
            if(sum_bitmask[j] == prefix[i]){
                if(i == 1){
                    dp[i][j] = 1;
                    v[i].push_back(j);
                }

                for(auto l : v[i-1]){
                    if((l | j) == j){
                        dp[i][j] = 1;
                        v[i].push_back(j);
                        // cerr << i << " : " << l << ' ' << j << endl;
                        break;
                    }
                }
            }
        }
    }
    
    bool ans = 0;
    for(int j = 0; j <= (1 << m); j++) ans |= dp[n][j];
    
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;

    // for(int i = 0; i <= n; i++){
    //     for(int j = 0; j <= (1 << m); j++){
    //         cerr << j << " : " << dp[i][j] << endl;
    //     }
    //     cerr << endl;
    // }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
        cerr << endl;
    }

    return 0;
}

/*
1 5
8
4 2 5 1 3

2 6
9 10
5 4 8 6 3 11

2 8
9 10
5 4 8 6 3 11 2 5
*/

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