제출 #1303872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303872		ChottuF	은행 (IZhO14_bank)	C++20	100 / 100	89 ms	8612 KiB

bank

#include <bits/stdc++.h>
using namespace std;

pair<int,int> dp[1<<20];

int main(){
    int n,m;
    cin >> n >> m;
    int arr[n];
    int note[m];
    for (int i = 0; i<n; i++){
        cin >> arr[i];
    }
    for (int i = 0; i<m; i++){
        cin >> note[i];
    }
    sort(arr,arr+n);
    sort(note,note+m);
    dp[0] = {0,0}; //we're at index 0, still there
    for (int s = 1; s<(1<<m); s++){
        dp[s] = {-1,-1}; //we want to maximise first
        for (int p = 0; p<m; p++){
            if ((s & (1<<p)) == 0) continue;
            int prv = s ^ (1<<p);
            if (dp[prv].first == -1 || dp[prv].second == -1) continue;
            auto [idx,lft] = dp[prv];
            if (lft + note[p] < arr[idx]){
                lft = lft+note[p];
            }
            else if (lft + note[p] == arr[idx]){
                lft = 0;
                idx++;
                if (idx == n){
                    cout << "YES\n";
                    return 0;
                }
            }
            else if (lft + note[p] > arr[idx]){
                continue;
            }
            dp[s] = max(dp[s], {idx,lft});
        }
    }
    cout << "NO\n";
    return 0;
}

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