제출 #1117753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117753		NguyenPhucThang	은행 (IZhO14_bank)	C++14	100 / 100	96 ms	9032 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vii;
typedef pair<int, pair<int, int>> piii;

#define forr(i, a, b) for (int i = (a); i <= (b); i++)
#define ford(i, a, b) for (int i = (a); i >= (b); i--)
#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }

const int base = 31;
const ll mod = 1e9 + 7; // 998244353;
const ll oo = (ll) 1e16;
const int N = 2e5 + 5;

int a[N], b[N], cover[(1 << 20)], leftover[(1 << 20)];

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);


    int n, m;
    cin >> n >> m;
    forr(i, 1, n) cin >> a[i];
    forr(i, 1, m) cin >> b[i];

    memset(cover, -1, sizeof cover);
    memset(leftover, -1, sizeof leftover);

    cover[0] = 0;
    leftover[0] = 0;

    forr(mask, 1, (1 << m) - 1) {
        forr(i, 1, m) {
            if (bit(mask, i - 1) == 0) continue;        
            int mask2 = mask ^ (1 << (i - 1));
            if (cover[mask2] == -1) continue;

            int tmp = leftover[mask2] + b[i];
            int nxt = a[cover[mask2] + 1];
            if (tmp < nxt) {
                cover[mask] = cover[mask2];
                leftover[mask] = tmp;
            }   
            else if (tmp == nxt) {
                cover[mask] = cover[mask2] + 1;
                leftover[mask] = 0;
            }     
        }
    }

    forr(mask, 0, (1 << m) - 1) {
        if (cover[mask] == n) {
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
    return 0;
}

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