제출 #1128173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128173		rasbery303	은행 (IZhO14_bank)	C++20	19 / 100	2 ms	840 KiB

bank

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 21;
int n, m, a[N], b[N];
pair<int, int> path[N][1001*N];
bool dp[N][N*1001], ok = true;

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= m; ++i)
        cin >> b[i];

    if (n>m){
        cout << "NO";
        return 0;
    }

    sort(b+1, b+m+1);

    for (int k = 1; k <= n; ++k){
        for (int i = 0; i <= m; ++i) for (int j = 0; j <= 1000*N; ++j) dp[i][j] = 0;

        dp[0][0] = 1;
        for (int i = 0; i < m; ++i){
            for (int val = 0; val < 1000*N; ++val){
                dp[i+1][val] |= dp[i][val];
                if (dp[i][val]) path[i+1][val] = {i, val};
                dp[i+1][val+b[i+1]] |= dp[i][val];
                if (dp[i][val]) path[i+1][val+b[i+1]] = {i, val};
            }
        }

        pair<int, int> st = {0, a[k]};
        for (int i = 1; i <= m; ++i){
            if (dp[i][a[k]]) {st.first = i; break;}
        }


        //cout << "st = " << st.first << "\tval = " << st.second << '\n';
        if (st.first==0) ok = 0;
        //cout << "ok = " << ok << "\n";
        if (ok==0) break;
        while (st.second != 0){
            int kl = st.first;
            st = path[st.first][st.second-b[st.first]];
            b[kl] = 0;
        }
    }
    
    cout << (ok? "YES" : "NO");
    return 0;
}  

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