제출 #1339003

#제출 시각아이디문제언어결과실행 시간메모리
1339003i_love_springBank (IZhO14_bank)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;
const int N = 1007;
int cnt[N], dp[20][1 << 20];
vector<int> a, b;
vector<int> f[20];

void solve() {
    int n, m;
    cin >> n >> m;

    for (int x, i = 0; i < n;i++)
        cin >> x, cnt[x]++;
    
    for (int x, i = 0; i < m;i++) {
        cin >> x;
        if (cnt[x] > 0) 
            cnt[x]--;
        else 
            b.push_back(x);
    }

    for (int i = 1; i < N;i++) 
        for (int j = 0; j < cnt[i];j++) 
            a.push_back(i);

    n = a.size();
    m = b.size();

    if (n * 2 > m)  
        return (void)(cout << "NO");

    vector<int> pref(n + 1);
    for (int i = 1; i <= n;i++)
        pref[i] = pref[i - 1] + a[i - 1];

    vector<int> dp(1 << m, -inf), rem(1 << m, -inf);
    dp[0] = rem[0] = 0;
    for (int mask = 0; mask < (1 << m);mask++) {
        if (dp[mask] == -inf)
            continue;
        for (int i = 0; i < m;i++) {
            if (mask >> i & 1) 
                continue;

            int j = dp[mask];
            if (j == n) 
                continue;
            int tar = pref[j + 1];
            int cur = b[j] + rem[mask];
            if (cur < tar) {
                dp[mask | (1 << i)] = j;
                rem[mask | (1 << i)] = cur;
            }
            if (cur == tar) {
                rem[mask | (1 << i)] = 0;
                dp[mask | (1 << i)] = j + 1;
            }
        }
        if (dp[mask] == n)
            return (void)(cout << "YES");
    } 

    cout << "NO";

}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...