제출 #722304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
722304		PagodePaiva	은행 (IZhO14_bank)	C++14	100 / 100	97 ms	8496 KiB

bank

		#include<bits/stdc++.h>
#define N 20
#define fr first
#define sc second

using namespace std;

int n, m;
int v[N], b[N];
pair <int, int> dp[(1 << N)];

bool comp(pair <int, int> a, pair <int, int> c){
    if(a.fr > c.fr) return true;
    if(a.fr < c.fr) return false;
    if(a.sc < c.sc) return true;
    return false;
}

int main(){
    cin >> m >> n;

    for(int i = 0;i < m;i++){
        cin >> b[i];
    }

    for(int i = 0;i < n;i++){
        cin >> v[i];
    }

    dp[0].fr = 0;
    dp[0].sc = 0;

    for(int mask = 1;mask < (1 << n);mask++){
        dp[mask].fr = dp[mask].sc = -1;

        for(int i = 0;i < n;i++){
            if((mask & (1 << i)) != 0){
                int s = mask^(1 << i);

                pair <int, int> aux;

                if(dp[s].sc + v[i] == b[dp[s].fr]){
                    aux.fr = dp[s].fr + 1;
                    aux.sc = 0;
                }

                else{
                    aux.fr = dp[s].fr;
                    aux.sc = dp[s].sc + v[i];
                }

                if(comp(aux, dp[mask])){
                    dp[mask] = aux;
                }
            }
        }

        // cout << mask << " " << dp[mask].fr << " " << dp[mask].sc << "\n";
    }

    cout << (dp[(1 << n)-1].fr == m ? "YES" : "NO") << "\n";

    return 0;
}

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