oj.uz

Submission #777723

# Submission time Handle Problem Language Result Execution time Memory
777723 2023-07-09T14:10:48 Z Sandarach151 Bank (IZhO14_bank) C++17
0 / 100
 54 ms 7392 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;
            int sum = 0;
            for(int j=0; j<20; j++){
                if((curstate & (1<<j))!=0){
                    sum+=notes[i];
                    if(sum>people[i]){
                        break;
                    }
                }
            }
            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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 4392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 7392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1332 KB Output isn't correct
2 Halted 0 ms 0 KB -