oj.uz

답안 #777722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777722 2023-07-09T14:07:41 Z Sandarach151 은행 (IZhO14_bank) C++17
0 / 100
 55 ms 7360 KB 
#include<bits/stdc++.h>
using namespace std;

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

int backtrack(int person, int curstate, int n){
    if(person==n){
        return true;
    }
    if(visited[person][curstate]){
        return false;
    }
    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;
            }
        }
    }
    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" : cout << "NO";

}

Compilation message

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

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 4368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 7360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1236 KB Output isn't correct
2 Halted 0 ms 0 KB -