제출 #873854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873854		AlphaMale06	Bank (IZhO14_bank)	C++14	19 / 100	79 ms	8528 KiB

bank

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int dp[1<<N], rest[1<<N];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i=0; i< n; i++)cin >> a[i];
    int b[m];
    for(int i=0; i < m; i++)cin >> b[i];
    sort(a, a+n);
    sort(b, b+m);
    int mask=1<<m;
    rest[0]=a[0];
    for(int i=1; i<mask; i++){
        int bestdp=0;
        int bestrest=10000;
        for(int j=0; j< m; j++){
            int bit=1<<j;
            if(i&bit){
                if(rest[i^bit]==b[j]){
                    if(bestdp<=dp[i^bit]){
                        bestdp=dp[i^bit]+1;
                        if(bestdp==n){
                            cout << "YES\n";
                            return 0;
                        }
                        else{
                            bestrest=a[bestdp];
                        }
                    }
                }
                else{
                    if(bestdp==dp[i^bit]){
                        if(rest[i^bit]-b[j]>0)bestrest=min(bestrest, rest[i^bit]-b[j]);
                    }
                }
            }
        }
        dp[i]=bestdp;
        rest[i]=bestrest;
    }
    if(dp[mask-1]==n)cout << "YES\n";
    else cout << "NO\n";
}

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