제출 #1229030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229030		LmaoLmao	은행 (IZhO14_bank)	C++20	100 / 100	666 ms	120416 KiB

bank

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

bool 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;
}

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