oj.uz

답안 #856185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856185 2023-10-02T19:01:44 Z ThylOne 은행 (IZhO14_bank) C++14
71 / 100
 74 ms 83536 KB 
#include<bits/stdc++.h>

using namespace std;
int n,m;
vector<int> salaries;
vector<int> billets;
#define BS bitset
bool mem[20][(1<<21)];
void initMem(){
	for(int i=0;i<20;i++){
		for(int j=0;j<(1<<21);j++){
			mem[i][j]=false;
		}
	}
}
bool solved(int pos,BS<20> bs){
	if(mem[pos][bs.to_ulong()]){
		return false;
	}
	mem[pos][bs.to_ulong()]=true;
	if(pos==n)return true;
	vector<int> index;
	for(int i=0;i<m;i++){
		if(!bs[i]){
			index.push_back(i);
		}
		
	}
	const int S = int(index.size());
	for(int i=0;i<(1<<S);i++){
		BS<20> bs2 = i;
		int sum=0;
		for(int j=0;j<S;j++){
			if(bs2[j]){
				sum+=billets[index[j]];
			}
			if(sum>salaries[pos])break;
		}
		
		if(sum==salaries[pos]){
			BS<20> cbs=bs;
			for(int j=0;j<S;j++){
				if(bs2[j]){
					cbs[index[j]]=1;
				}
				
			}
			if(solved(pos+1,cbs)){
					return true;
				}
		}
	}
	
	
	return false;
}
signed main(){
	initMem();
	cin>>n>>m;
	salaries.resize(n);
	billets.resize(m);
	for(int i=0;i<n;i++){
		cin>>salaries[i];
	}
	for(int i=0;i<m;i++){
		cin>>billets[i];
	}
	sort(billets.begin(),billets.end());
	
	if(solved(0,0)){
		cout<<"YES\n";
	}else{
		cout<<"NO\n";
	}
	return 0;
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 41304 KB Output is correct
2 Correct 6 ms 41308 KB Output is correct
3 Correct 6 ms 41376 KB Output is correct
4 Correct 5 ms 41308 KB Output is correct
5 Correct 18 ms 41304 KB Output is correct
6 Correct 5 ms 41304 KB Output is correct
7 Correct 6 ms 41308 KB Output is correct
8 Correct 7 ms 41332 KB Output is correct
9 Correct 74 ms 41448 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 41304 KB Output is correct
2 Correct 6 ms 41308 KB Output is correct
3 Correct 5 ms 41308 KB Output is correct
4 Correct 5 ms 41308 KB Output is correct
5 Correct 6 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 5 ms 41308 KB Output is correct
8 Correct 5 ms 41356 KB Output is correct
9 Correct 5 ms 41304 KB Output is correct
10 Correct 6 ms 41308 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 41304 KB Output is correct
2 Correct 6 ms 41304 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 5 ms 41332 KB Output is correct
5 Correct 6 ms 41308 KB Output is correct
6 Correct 6 ms 41336 KB Output is correct
7 Correct 5 ms 41308 KB Output is correct
8 Correct 5 ms 41308 KB Output is correct
9 Correct 5 ms 41376 KB Output is correct
10 Correct 6 ms 41308 KB Output is correct
11 Correct 6 ms 41304 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 41304 KB Output is correct
2 Correct 6 ms 41308 KB Output is correct
3 Correct 6 ms 41376 KB Output is correct
4 Correct 5 ms 41308 KB Output is correct
5 Correct 18 ms 41304 KB Output is correct
6 Correct 5 ms 41304 KB Output is correct
7 Correct 6 ms 41308 KB Output is correct
8 Correct 7 ms 41332 KB Output is correct
9 Correct 74 ms 41448 KB Output is correct
10 Correct 5 ms 41304 KB Output is correct
11 Correct 6 ms 41308 KB Output is correct
12 Correct 5 ms 41308 KB Output is correct
13 Correct 5 ms 41308 KB Output is correct
14 Correct 6 ms 41308 KB Output is correct
15 Correct 5 ms 41308 KB Output is correct
16 Correct 5 ms 41308 KB Output is correct
17 Correct 5 ms 41356 KB Output is correct
18 Correct 5 ms 41304 KB Output is correct
19 Correct 6 ms 41308 KB Output is correct
20 Correct 6 ms 41304 KB Output is correct
21 Correct 6 ms 41304 KB Output is correct
22 Correct 6 ms 41308 KB Output is correct
23 Correct 5 ms 41332 KB Output is correct
24 Correct 6 ms 41308 KB Output is correct
25 Correct 6 ms 41336 KB Output is correct
26 Correct 5 ms 41308 KB Output is correct
27 Correct 5 ms 41308 KB Output is correct
28 Correct 5 ms 41376 KB Output is correct
29 Correct 6 ms 41308 KB Output is correct
30 Correct 6 ms 41304 KB Output is correct
31 Correct 20 ms 41308 KB Output is correct
32 Correct 18 ms 41364 KB Output is correct
33 Correct 6 ms 41308 KB Output is correct
34 Correct 7 ms 41304 KB Output is correct
35 Correct 17 ms 41308 KB Output is correct
36 Runtime error 36 ms 83536 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -