제출 #873857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873857		AlphaMale06	은행 (IZhO14_bank)	C++14	100 / 100	90 ms	8620 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(rest[i^bit]>b[j]){
                    if(bestdp==dp[i^bit]){
                        bestrest=min(bestrest, rest[i^bit]-b[j]);
                    }
                    else if(bestdp<dp[i^bit]){
                        bestdp=dp[i^bit];
                        bestrest=rest[i^bit]-b[j];
                    }
                }
            }
        }
        dp[i]=bestdp;
        rest[i]=min(bestrest, a[dp[i]]);
    }
    cout << "NO\n";
}

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