Submission #777728

#	Time	Username	Problem	Language	Result	Execution time	Memory
777728		Sandarach151	Bank (IZhO14_bank)	C++17	100 / 100	995 ms	34928 KiB

bank

#include<bits/stdc++.h>
using namespace std;

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

bool 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 (stderr)

bank.cpp: In function 'bool 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 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29