제출 #722304

#제출 시각아이디문제언어결과실행 시간메모리
722304PagodePaivaBank (IZhO14_bank)C++14
100 / 100
97 ms8496 KiB
		#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...