Submission #171402

#	Time	Username	Problem	Language	Result	Execution time	Memory
171402		VEGAnn	은행 (IZhO14_bank)	C++14	52 / 100	87 ms	2552 KiB

bank

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pll pair<ll, ll>
using namespace std;
typedef long long ll;
const ll OO = 1e18;
const int N = 14;
const int M = 1010;
const int PW = (1 << N);
int n, m, a[N], b[N], mm, sum[PW];
bool mk[2][PW];
bitset<M> msk[PW], clr;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("penguins.in","r",stdin); freopen("penguins.out","w",stdout);
//    freopen("in.txt","r",stdin);
    cin >> n >> m;
    mm = (1 << m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    bool was = 1;
    mk[1][0] = 1;

    for (int i = 1; i < mm; i++){
        for (int j = 0; j < m; j++)
            if ((i & (1 << j))){
                sum[i] = sum[i ^ (1 << j)] + b[j];
                break;
            }
    }

    for (int it = 0; it < n; it++){
        int cit = (it & 1);
        was = 0;
        fill(mk[cit], mk[cit] + mm, false);

        for (int mask = 0; mask < mm; mask++) {
            msk[mask] = clr;
            if (mk[cit ^ 1][mask])
                msk[mask][M - 1] = 1;
        }

        for (int k = 0; k < m; k++)
            for (int mask = 0; mask < mm; mask++) {
                int nw = (mask ^ (1 << k));
                if ((mask & (1 << k)) && sum[mask] - sum[nw] < M) {
                    msk[mask] |= (msk[nw] >> (sum[mask] - sum[nw]));
                }
            }

        for (int mask = 1; mask < mm; mask++){
            if (sum[mask] < a[it]) continue;
//            int sm = sum[mask] - a[it];
            if (msk[mask][M - 1 - a[it]]) {
                mk[cit][mask] = 1;
                was = 1;
            }
        }
    }

    cout << (was ? "YES" : "NO");
    return 0;
}

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