# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
566158 | racsosabe | 은행 (IZhO14_bank) | C++14 | 434 ms | 26752 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace::std;
const int N = 20 + 5;
const int MASK = 1 << 20;
int n;
int m;
int neg;
int a[N];
int b[N];
int sum[MASK];
bool vis[MASK];
int nxt[2][MASK];
int memo[2][MASK];
void preprocess(){
while(neg < n and a[neg] < 0) neg++;
for(int mask = 1; mask < (1 << m); mask++){
sum[mask] = sum[mask & (mask - 1)] + b[__builtin_ctz(mask)];
int lo = 0, hi = neg;
while(lo < hi){
int mi = lo + (hi - lo) / 2;
if(a[mi] < sum[mask]) hi = mi;
else lo = mi + 1;
}
nxt[0][mask] = a[lo];
lo = neg, hi = n;
while(lo < hi){
int mi = lo + (hi - lo) / 2;
if(sum[mask] <= a[mi]) lo = mi + 1;
else hi = mi;
}
nxt[1][mask] = a[lo];
}
}
vector<int> get_order(){
queue<int> Q;
Q.emplace(0);
vector<int> res;
while(!Q.empty()){
int mask = Q.front(); Q.pop();
res.emplace_back(mask);
for(int i = 0, p = 1; i < m; i++, p <<= 1){
if(mask & p) continue;
if(vis[mask | p]) continue;
Q.emplace(mask | p);
vis[mask | p] = true;
}
}
return res;
}
bool solve(){
vector<int> order = get_order();
for(int mask = 0, l = 1 << m; mask < l; mask++) vis[mask] = false;
for(int at = 0; at + 1 < order.size(); at++){
int mask = order[at];
for(int i = 0, p = 1; i < m; i++, p <<= 1){
if(mask & p) continue;
int new_sum = sum[mask | p];
int val = memo[0][mask];
if(new_sum == nxt[0][sum[mask]]) val += 1;
memo[0][mask | p] = max(memo[0][mask | p], val);
}
}
for(int at = 0; at < order.size(); at++){
int mask = order[at];
for(int i = 0, p = 1; i < m; i++, p <<= 1){
if(mask & p) continue;
int new_sum = sum[mask | p];
int val = memo[0][mask];
if(new_sum == nxt[1][sum[mask]]) val += 1;
memo[1][mask | p] = max(memo[1][mask | p], val);
}
}
for(int at = 0; at + 1 < order.size(); at++){
int mask = order[at];
for(int i = 0, p = 1; i < m; i++, p <<= 1){
if(mask & p) continue;
int new_sum = sum[mask | p];
int val = memo[1][mask];
if(new_sum == nxt[1][sum[mask]]) val += 1;
memo[1][mask | p] = max(memo[1][mask | p], val);
}
}
for(int mask = 0, l = 1 << m; mask < l; mask++){
if(memo[0][mask] == n) return true;
if(memo[1][mask] == n) return true;
}
return false;
}
int main(){
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", a + i);
for(int i = 0; i < m; i++) scanf("%d", b + i);
sort(a, a + n);
for(int i = 1; i < n; i++) a[i] += a[i - 1];
preprocess();
puts(solve() ? "YES" : "NO");
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |