제출 #1257347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257347		iamhereforfun	은행 (IZhO14_bank)	C++20	100 / 100	102 ms	8644 KiB

bank

// Starcraft 2 enjoyer + luv kd //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 20;
const int M = 4e5 + 5;
const int S = 640;
const int O = 2e5 + 5;
const int K = 15;
const int LG = 21;
const int P = 37;
const int INF = 1e9 + 5;
const int MOD = 998244353;
const int nx[] = {0, 1, 0, -1}, ny[] = {1, 0, -1, 0};

int n, m, a[N], b[N], pref[1 << N], le[1 << N];

void solve()
{
    cin >> n >> m;
    for(int x = 0; x < n; x++)
    {
        cin >> a[x];
    }
    for(int x = 0; x < m; x++)
    {
        cin >> b[x];
    }
    memset(pref, -1, sizeof(pref));
    memset(le, 0, sizeof(le));
    pref[0] = 0;
    le[0] = 0;
    for(int x = 1; x < (1 << m); x++)
    {
        for(int y = 0; y < m; y++)
        {
            if(!(x >> y & 1)) continue;
            int pre = x & ~(1 << y), tot, val;
            if(pref[pre] == -1) continue;
            tot = le[pre] + b[y];
            val = a[pref[pre]];
            if(tot < val)
            {
                pref[x] = pref[pre];
                le[x] = tot;
            }
            else if(tot == val)
            {
                pref[x] = pref[pre] + 1;
                le[x] = 0;
            }
        }
        if(pref[x] == n)
        {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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