이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const ll INF = numeric_limits<ll>::max();
const int inf = numeric_limits<int>::max();
const char nl = '\n', sp = ' ';
ll cantor_hash(ll x, ll y){
return (((x + y) * (x + y + 1)) >> 1) + y;
}
unordered_map<ll, vector<ll> > ks;
void get_key_signature(ll orig, ll curr, int mask, int id,vector<ll> &billz){
if(curr == 0){
ks[orig].push_back(mask);
return;
}
if(id == billz.size()){
return;
}
if(curr - billz[id] >= 0){
get_key_signature(orig, curr - billz[id], mask + (1 << id), id + 1, billz);
}
get_key_signature(orig, curr, mask, id + 1, billz);
}
unordered_map<ll, bool> vis;
bool pathexists(int node, int mask,vector<ll> &salary, vector<ll> &billz){
if(node == salary.size()){
return true;
} else {
if(vis.count(cantor_hash(node,mask))){
return vis[cantor_hash(node,mask)];
}
bool flag = false;
for(int kbitmask: ks[salary[node]]){
if((mask & kbitmask) == kbitmask){
flag = flag | pathexists(node + 1, mask ^ kbitmask,salary, billz);
}
}
vis[cantor_hash(node,mask)] = flag;
return flag;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<ll> salary;
vector<ll> billz;
ll num;
for(int i = 0; i < N; i++){
cin >> num;
ks[num] = vector<ll>();
salary.push_back(num);
}
ll totalbillz = 0;
for(int i = 0; i < M; i++){
cin >> num;
totalbillz += num;
billz.push_back(num);
}
// sort(billz.begin(),billz.end());
for(ll elem: salary){
get_key_signature(elem,elem,0,0,billz);
}
bool ans = pathexists(0,(1 << M) - 1, salary, billz);
if(ans) {
cout << "YES" << nl;
} else {
cout << "NO" << nl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
bank.cpp: In function 'void get_key_signature(ll, ll, int, int, std::vector<long long int>&)':
bank.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | if(id == billz.size()){
| ~~~^~~~~~~~~~~~~~~
bank.cpp: In function 'bool pathexists(int, int, std::vector<long long int>&, std::vector<long long int>&)':
bank.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | if(node == salary.size()){
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |