oj.uz

Submission #739958

# Submission time Handle Problem Language Result Execution time Memory
739958 2023-05-11T18:31:20 Z Toxtaq Bank (IZhO14_bank) C++17
25 / 100
 117 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>people, banknotes;
vector<vector<vector<short>>>table;
short rec(int indx, int mask, int cur_people){
    if(indx == n)return 1;
    if(cur_people < 0)return 0;
    if(cur_people == 0){
        indx++;
        if(indx == n)return 1;
        cur_people = people[indx];
    }
    bool res = 0;
    if(table[indx][mask][cur_people] != -1)return table[indx][mask][cur_people];
    for(int i = 0;i < m;++i){
        if(mask & (1 << i)){
            res = res | rec(indx, mask ^ (1 << i), cur_people - banknotes[i]);
        }
    }
    return table[indx][mask][cur_people] = res;
}
int main()
{
    cin >> n >> m;
    people.resize(n);
    banknotes.resize(m);
    table.assign(n, vector<vector<short>>((1 << m), vector<short>(1001, -1)));
    for(int i = 0;i < n;++i)cin >> people[i];
    for(int i = 0;i < m;++i)cin >> banknotes[i];
    if(rec(0, (1 << m) - 1, people[0])){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 67 ms 131096 KB Output is correct
5 Runtime error 100 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 4 ms 8440 KB Output is correct
3 Correct 3 ms 6356 KB Output is correct
4 Correct 5 ms 10412 KB Output is correct
5 Correct 8 ms 16596 KB Output is correct
6 Correct 6 ms 12460 KB Output is correct
7 Correct 4 ms 8404 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 4 ms 8404 KB Output is correct
10 Correct 6 ms 12500 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 261884 KB Output is correct
2 Correct 59 ms 131072 KB Output is correct
3 Runtime error 117 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 67 ms 131096 KB Output is correct
5 Runtime error 100 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -