oj.uz

Submission #676325

# Submission time Handle Problem Language Result Execution time Memory
676325 2022-12-30T10:36:41 Z murad_2005 Bank (IZhO14_bank) C++14
19 / 100
 134 ms 118212 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define pllll pair<ll, ll>
#define pb push_back
#define all(v) v.begin(), v.end()
#define size(v) v.size()
#define INF 2e18
#define f first
#define s second

using namespace std;

const int up = 20;

int n, m;
vector<int>costMask[20005];
vector<vector<int>>dp((1 << up), vector<int>(n + 1));
vector<int>a, b;

int Bank(int mask, int i){
    if(i == 0) return 1;
    if(dp[mask][i] != -1) return dp[mask][i];

    for(int Submask : costMask[a[i]]){
        if((mask & Submask) == Submask){
            if(Bank(mask ^ Submask, i - 1)){
                return dp[mask][i] = 1;
            }
        }
    }
    return dp[mask][i] = 0;
}

void solve(){

    cin >> n >> m;
    a.resize(n + 1), b.resize(m + 1);
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }for(int i = 1; i <= m; ++i){
        cin >> b[i];
    }
    for(int mask = 0; mask < (1 << m); ++mask){
        int Total = 0;
        for(int i = 0; i < m; ++i){
            if(mask & (1 << i)){
                Total += b[i + 1];
            }
        }
        costMask[Total].pb(mask);
    }
    for(int mask = 0; mask < (1 << m); mask++){
        for(int i = 1; i <= n; ++i){
            dp[mask][i] = -1;
        }
    }

    if(Bank((1 << m) - 1, n)) cout << "YES\n";
    else cout << "NO\n";
}

int main(){
    int t;
    t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 58192 KB Output is correct
2 Correct 60 ms 58216 KB Output is correct
3 Correct 50 ms 58232 KB Output is correct
4 Correct 53 ms 58428 KB Output is correct
5 Correct 134 ms 64664 KB Output is correct
6 Correct 52 ms 58188 KB Output is correct
7 Correct 55 ms 58180 KB Output is correct
8 Correct 128 ms 63936 KB Output is correct
9 Correct 126 ms 64272 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 58188 KB Output is correct
2 Correct 53 ms 58112 KB Output is correct
3 Correct 53 ms 58148 KB Output is correct
4 Correct 53 ms 58220 KB Output is correct
5 Runtime error 93 ms 117836 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 106 ms 118212 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 58192 KB Output is correct
2 Correct 60 ms 58216 KB Output is correct
3 Correct 50 ms 58232 KB Output is correct
4 Correct 53 ms 58428 KB Output is correct
5 Correct 134 ms 64664 KB Output is correct
6 Correct 52 ms 58188 KB Output is correct
7 Correct 55 ms 58180 KB Output is correct
8 Correct 128 ms 63936 KB Output is correct
9 Correct 126 ms 64272 KB Output is correct
10 Correct 52 ms 58188 KB Output is correct
11 Correct 53 ms 58112 KB Output is correct
12 Correct 53 ms 58148 KB Output is correct
13 Correct 53 ms 58220 KB Output is correct
14 Runtime error 93 ms 117836 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -