Submission #1214378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214378		euclid	은행 (IZhO14_bank)	C++20	100 / 100	97 ms	8720 KiB

bank

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vl vector<ll>

int n, m;
const int MN = 23, MS = (1<<20)+3;
int a[MN], b[MN];
int dp[MS][2]; //dp[s][0] - maximum prefix of workers payable with the notes in s
//dp[s][1] - after paying the prefix dp[s][1], the remaining amount of money

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    bool pos = false;
    for(int s = 1; s < (1<<m); s++) {
        for(int j = 0; j < m; j++) {
            if((1<<j)&s) {
                int f = dp[s^(1<<j)][0], g = dp[s^(1<<j)][1];
                if(f == n) continue;
                if(a[f+1]==g+b[j+1]) dp[s][0] = f+1, dp[s][1] = 0;
                else {
                    if(f >= dp[s][0]) dp[s][0] = f, dp[s][1] = g+b[j+1];
                }
            }
        }
//        cout << s << ' ' << dp[s][0] << ' ' << dp[s][1] << '\n';
        if(dp[s][0] == n) pos = true;
    }
    cout << (pos ? "YES" : "NO") << '\n';

}

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