제출 #1121042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1121042		akacool445k	은행 (IZhO14_bank)	C++17	100 / 100	105 ms	8784 KiB

bank

#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;
}

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