Submission #1121042

#TimeUsernameProblemLanguageResultExecution timeMemory
1121042akacool445k은행 (IZhO14_bank)C++17
100 / 100
105 ms8784 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
// #define int long long
#define pint pair<int, int>
#define vint vector<pair<int, int>>
const int mod = 1e9 + 7;
const int shrek = 4000 * 20;
const int say = INT_MAX;
const int gex = INT_MIN;
const long long oo = 1e18;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("guard.in", "r", stdin);
	// freopen("guard.out", "w", stdout);
    int n, m; cin >> n >> m;
    int a[n], b[m];
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    int dp[1 << m];
    int extra[1 << m];
    for(int i = 0; i < (1 << m); i++) {
        dp[i] = -1;
        extra[i] = -1;
    }
    dp[0] = 0;
    extra[0] = 0;
    for(int msk = 0; msk < (1 << m); msk++) {
        for(int i = 0; i < m; i++) {
            if((msk & (1 << i)) == 0) continue;
            int pre = msk ^ (1 << i);
            if(dp[pre] == -1) continue;
            int pp = a[dp[pre]];
            int qq = extra[pre] + b[i];
            if(qq < pp) {
                dp[msk] = dp[pre];
                extra[msk] = qq;
            }
            else if(pp == qq) {
                dp[msk] = dp[pre] + 1;
                extra[msk] = 0;
            }
        }
        if(dp[msk] == n) {
            cout << "YES" << '\n';
            return 0;
        }
    }
    cout << "NO" << '\n';
    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...