oj.uz

답안 #777724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777724 2023-07-09T14:15:17 Z Sandarach151 은행 (IZhO14_bank) C++17
46 / 100
 1000 ms 14672 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<m; j++){
                if((curstate & (1<<j))!=0){
                    sum+=notes[j];
                    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
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1492 KB Output is correct
2 Correct 7 ms 1308 KB Output is correct
3 Correct 33 ms 1284 KB Output is correct
4 Correct 45 ms 1312 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 46 ms 1376 KB Output is correct
8 Correct 63 ms 1292 KB Output is correct
9 Correct 70 ms 1272 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 5220 KB Output is correct
2 Correct 40 ms 3400 KB Output is correct
3 Correct 44 ms 2328 KB Output is correct
4 Correct 101 ms 7500 KB Output is correct
5 Correct 55 ms 11640 KB Output is correct
6 Correct 31 ms 5436 KB Output is correct
7 Correct 57 ms 3852 KB Output is correct
8 Execution timed out 1087 ms 6948 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 8204 KB Output is correct
2 Correct 140 ms 3356 KB Output is correct
3 Correct 80 ms 10560 KB Output is correct
4 Correct 65 ms 14672 KB Output is correct
5 Correct 67 ms 11528 KB Output is correct
6 Correct 19 ms 5324 KB Output is correct
7 Correct 98 ms 4860 KB Output is correct
8 Correct 98 ms 3632 KB Output is correct
9 Correct 68 ms 8444 KB Output is correct
10 Correct 67 ms 8460 KB Output is correct
11 Correct 827 ms 14652 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1492 KB Output is correct
2 Correct 7 ms 1308 KB Output is correct
3 Correct 33 ms 1284 KB Output is correct
4 Correct 45 ms 1312 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 4 ms 1236 KB Output is correct
7 Correct 46 ms 1376 KB Output is correct
8 Correct 63 ms 1292 KB Output is correct
9 Correct 70 ms 1272 KB Output is correct
10 Correct 46 ms 5220 KB Output is correct
11 Correct 40 ms 3400 KB Output is correct
12 Correct 44 ms 2328 KB Output is correct
13 Correct 101 ms 7500 KB Output is correct
14 Correct 55 ms 11640 KB Output is correct
15 Correct 31 ms 5436 KB Output is correct
16 Correct 57 ms 3852 KB Output is correct
17 Execution timed out 1087 ms 6948 KB Time limit exceeded
18 Halted 0 ms 0 KB -