제출 #671846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671846		moday_morning	은행 (IZhO14_bank)	C++17	71 / 100	1090 ms	186104 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define fr first
#define sc second
#define pb push_back
using namespace std;

int n, m;
int a[20], b[20], sum[20], s[1 << 20];
bool c[1 << 20][21];
vector <int> v[1<<20];
 
void update (int i, int j) {
    if (c[i][j]) {
        return;
    }
    c[i][j]=true;
    for (auto x : v[i]) {
        update((i | (1 << x)), j);
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0) {
            sum[i] = sum[i-1];
        }
        sum[i] += a[i];
    }
    for (int j = 0; j < m; j++) {
        cin >> b[j];
    }
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) {
                s[i] += b[j];
            }
            else {
                v[i].push_back(j);
            }
        }
    }
    update(0, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << m); j++) {
            int x = 0;
            if (i > 0) {
                x = sum[i-1];
            }
            if (c[j][i] && s[j] - x == a[i]) {
                update(j, i+1);
            }
            else {
                c[j][i]=false;
            }
        }
    }
    for (int j = 0; j < (1 << m); j++) {
        if (c[j][n]) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

signed main() {
//    usaco("triangles");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

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