Submission #360656

#	Time	Username	Problem	Language	Result	Execution time	Memory
360656		Seanliu	Bank (IZhO14_bank)	C++14	100 / 100	127 ms	63084 KiB

bank

#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 22;
int N, M, a[maxN], b[maxN], dp[maxN][1 << maxN], has[maxN], head, cnt, sum[1 << maxN], log[1 << maxN], pre[maxN];

int main(){
    for(int i = 0; i < maxN; i++) log[1 << i] = i;
    cin >> N >> M;
    for(int i = 1; i <= N; i++) cin >> a[i];
    for(int i = 0; i < M; i++) cin >> b[i];

    for(int i = 1; i <= N; i++) pre[i] = pre[i - 1] + a[i];
    for(int i = 1; i < (1 << M); i++){
        sum[i] = sum[i - (i & -i)] + b[log[i & -i]];
    }
    dp[1][0] = true;
    int ans = 0;
    for(int i = 1; i <= N; i++){
        for(int m = 1; m < (1 << M); m++){
            int cur = m;
            if(pre[i] < sum[m]) continue;
            if(pre[i - 1] > sum[m]) continue;
            while(cur){
                int id = log[cur & -cur];
                cur -= cur & -cur;
                if(dp[i][m - (1 << id)]) dp[i][m] = 1;
            }
            if(dp[i][m]){

                if(sum[m] == pre[i]) dp[i + 1][m] = 1;
                if(sum[m] == pre[N] && i == N && dp[i + 1][m]) ans = 1;
            }
        }
    }
    cout << (ans ? "YES" : "NO") <<endl;
}

Compilation message (stderr)

bank.cpp:6:88: warning: built-in function 'log' declared as non-function [-Wbuiltin-declaration-mismatch]
    6 | int N, M, a[maxN], b[maxN], dp[maxN][1 << maxN], has[maxN], head, cnt, sum[1 << maxN], log[1 << maxN], pre[maxN];
      |                                                                                        ^~~

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