oj.uz

Submission #777726

# Submission time Handle Problem Language Result Execution time Memory
777726 2023-07-09T14:18:09 Z Sandarach151 Bank (IZhO14_bank) C++17
46 / 100
 1000 ms 14676 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> states[20];
bool visited[20][1<<20];
bool ans[20][1<<20];

int backtrack(int person, int curstate, int n){
    if(person==n){
        return true;
    }
    if(visited[person][curstate]){
        return ans[person][curstate];
    }
    visited[person][curstate] = true;
    bool res = false;
    for(int i=0; i<states[person].size(); i++){
        if((states[person][i] & curstate)==0){
            res = res | backtrack(person+1, (states[person][i] | curstate), n);
            if(res==true){
                break;
            }
        }
    }
    ans[person][curstate]=res;
    return res;
}

int main(){
    int n, m;
    cin >> n >> m;
    int people[n];
    int notes[m];
    for(int i=0; i<n; i++){
        cin >> people[i];
    }
    for(int i=0; i<m; i++){
        cin >> notes[i];
    }
    for(int i=0; i<n; i++){
        for(int curstate = 0; curstate < (1<<20); curstate++){
            visited[i][curstate]=false;
        }
    }
    for(int curstate = 0; curstate < (1<<20); curstate++){
        int sum = 0;
        for(int j=0; j<m; j++){
            if((curstate & (1<<j))!=0){
                sum+=notes[j];
            }
        }
        for(int i=0; i<n; i++){
            if(sum==people[i]){
                states[i].push_back(curstate);
            }
        }
    }
    backtrack(0, 0, n) ? cout << "YES\n" : cout << "NO\n";

}

Compilation message

bank.cpp: In function 'int backtrack(int, int, int)':
bank.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0; i<states[person].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1492 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 37 ms 1364 KB Output is correct
4 Correct 56 ms 1360 KB Output is correct
5 Correct 65 ms 1316 KB Output is correct
6 Correct 37 ms 1316 KB Output is correct
7 Correct 48 ms 1348 KB Output is correct
8 Correct 63 ms 1380 KB Output is correct
9 Correct 72 ms 1324 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5188 KB Output is correct
2 Correct 40 ms 3464 KB Output is correct
3 Correct 39 ms 2368 KB Output is correct
4 Correct 123 ms 7552 KB Output is correct
5 Correct 60 ms 11624 KB Output is correct
6 Correct 41 ms 5532 KB Output is correct
7 Correct 41 ms 3772 KB Output is correct
8 Execution timed out 1082 ms 7268 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8272 KB Output is correct
2 Correct 57 ms 3396 KB Output is correct
3 Correct 64 ms 10552 KB Output is correct
4 Correct 66 ms 14676 KB Output is correct
5 Correct 64 ms 11592 KB Output is correct
6 Correct 60 ms 5424 KB Output is correct
7 Correct 59 ms 4928 KB Output is correct
8 Correct 58 ms 3640 KB Output is correct
9 Correct 62 ms 8520 KB Output is correct
10 Correct 62 ms 8520 KB Output is correct
11 Correct 67 ms 14548 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1492 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 37 ms 1364 KB Output is correct
4 Correct 56 ms 1360 KB Output is correct
5 Correct 65 ms 1316 KB Output is correct
6 Correct 37 ms 1316 KB Output is correct
7 Correct 48 ms 1348 KB Output is correct
8 Correct 63 ms 1380 KB Output is correct
9 Correct 72 ms 1324 KB Output is correct
10 Correct 41 ms 5188 KB Output is correct
11 Correct 40 ms 3464 KB Output is correct
12 Correct 39 ms 2368 KB Output is correct
13 Correct 123 ms 7552 KB Output is correct
14 Correct 60 ms 11624 KB Output is correct
15 Correct 41 ms 5532 KB Output is correct
16 Correct 41 ms 3772 KB Output is correct
17 Execution timed out 1082 ms 7268 KB Time limit exceeded
18 Halted 0 ms 0 KB -