제출 #1002343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002343		Duongkobeo	은행 (IZhO14_bank)	C++17	19 / 100	73 ms	17700 KiB

bank

#include<bits/stdc++.h>
#pragma GCC optimize("03,unroll-loops")
#pragma GCC target("avx2,bmi2,bmi,lzcnt,popcnt")
#define endl "\n"
#define rs resize
#define pb push_back
#define gcd __gcd
using namespace std;
vector<vector<int>> vv;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m; cin >> n >> m;
    vector<int> a, b;
    a.rs(n), b.rs(m), vv.rs(30);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    pair<int, int> p[(1 << m)];
    int visited[1 << m];
    memset(visited, 0, sizeof(visited));
    visited[0] = 1, p[0] = {0, 0};
    for (int i = 0; i < (1 << m); ++i) vv[__builtin_popcount(i)].pb(i);
    for (int i = 0; i < m; ++i) {
        for (auto it : vv[i]) {
            if (visited[it]) {
                if (p[it].first == n) {
                    cout << "YES";
                    return 0;
                }
                int x = p[it].first;
                for (int j = 0; j < m; ++j) {
                    int y = it | (1 << j);
                    if (it - y) {
                        if (p[it].second + b[j] > a[x]) continue;
                        visited[y] = 1;
                        p[y] = {x, p[it].second + b[j]};
                        if (a[x] == p[it].second + b[j]) p[y] = {x + 1, 0};
                    }
                }
            }
        }
    }
    cout << "NO";
    return 0;
}

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