# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
566158 | racsosabe | Bank (IZhO14_bank) | C++14 | 434 ms | 26752 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
Compilation message (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... |