제출 #1229000

#제출 시각아이디문제언어결과실행 시간메모리
1229000LmaoLmao은행 (IZhO14_bank)C++20
100 / 100
754 ms168640 KiB
#include <bits/stdc++.h>
#define name "a"
//#define int long long
#define fi first
#define se second
using namespace std;

using ii=pair<int,int>;

int dp[21][1<<20];
int a[21];
int pre[21];
int b[20];
int sum[1<<20];
vector<int> adj[1<<20];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        pre[i]=pre[i-1]+a[i];
    }
    for(int i=0;i<m;i++) {
        cin >> b[i];
    }
    for(int i=0;i<(1<<m);i++) {
        for(int j=0;j<m;j++) {
            if((i >> j & 1)==1) {
                sum[i]+=b[j];
                adj[i].push_back(j);
            }
        }
        //cout << sum[i] << endl;
        dp[0][i]=1;
    }
    for(int i=1;i<=n;++i) {
        for(int j=1;j < (1 << m);++j) {
            //cout << j << ' ';
            for(int k:adj[j]) {
                if(dp[i-1][j^(1<<k)]) {
                    dp[i][j]|=(1&(sum[j]==pre[i]));
                }
                if(dp[i][j^(1<<k)]) {
                    dp[i][j]|=1;
                }
            }
            //cout<< ' ' << dp[i][j] << ' ' << sum[j] << endl;
        }
    }
    if(dp[n][(1<<m)-1]) cout << "YES"; else cout << "NO";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...