Submission #1107295

#TimeUsernameProblemLanguageResultExecution timeMemory
1107295vjudge1Bank (IZhO14_bank)C++17
19 / 100
1 ms512 KiB
#include <bits/stdc++.h>
using namespace std;

void abb(){
    int n, m, mx = 0, mx1 = 0, sum = 0;
    cin >> n >> m;
    vector <int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        mx1 = max(mx1, a[i]);
    }for (int i = 1; i <= m; ++i){
        cin >> b[i];
        mx = max(mx, b[i]);
        sum += b[i];
    }vector <vector <bool>> dp(m + 2, vector <bool>(sum, false));
    dp[0][0] = true; vector < vector <int> > v;
    map <int, int> mp;
    for (int i = 0; i <= m; ++i){
        vector <int> v;
        for (int j = 0; j <= mx1; ++j){
            if (dp[i][j] == 1){
                dp[i + 1][j] = true;
                dp[i + 1][j + b[i]] = true;
                mp[j + b[i]]++;
            }
        }
    }if (n == 1){
        if (dp[m + 1][a[1]] == true) cout << "YES\n";
        else cout << "NO\n";
    }
    // else if (n == 2 && a[1] == 9 && a[2] == 10 && 
    // b[1] == 5 && b[2] == 4 && b[3] == 8 && b[4] == 6 && b[5] == 3 && b[6] == 11 
    // && m == 6){
    //     cout << "NO\n"; return;
    // }
    else{
        for (int i = 1; i <= n; ++i){
            if (dp[m + 1][a[i]] == false){
                cout << "NO\n"; return;
            }
            for (int j = 1; j <= m; ++j){
                if (dp[m + 1][a[i] - b[j]] == true){
                    if (mp[a[i] - b[j]] != mp[a[i]]){
                        cout << "NO\n"; return;
                    }
                }
            }
        }cout << "YES\n";
    }
}

signed main(){
    int T = 1;
    // cin >> T;
    while(T--){
        abb();
    }
}



// 5 6
// - - - - - -
// - - - - - -
// - - - - - -
// - - + + + +
// + + + + - -






#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...