# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
565560 | racsosabe | 은행 (IZhO14_bank) | C++14 | 8 ms | 4576 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace::std;
const int N = 20 + 5;
const int MAX = 1000 * 20 + 5;
const int MASK = 1 << 20;
int n;
int m;
int a[N];
int b[N];
int nxt[MAX];
int sum[MASK];
int memo[MASK];
bool vis[MASK];
void preprocess(){
for(int i = 0; i < n; i++){
nxt[a[i]] = a[i];
}
int last = MAX;
for(int i = MAX - 1; i >= 0; i--){
if(nxt[i] == i) last = i;
nxt[i] = last;
}
for(int mask = 1; mask < 1 << m; mask++){
sum[mask] = sum[mask & (mask - 1)] + b[__builtin_ctz(mask)];
}
}
bool solve(){
queue<int> Q;
Q.emplace(0);
while(!Q.empty()){
int mask = Q.front(); Q.pop();
for(int i = 0, p = 1; i < m; i++, p <<= 1){
if(mask & p) continue;
int new_sum = sum[mask] + b[i];
if(new_sum == nxt[sum[mask] + 1]) memo[mask | p] = max(memo[mask | p], 1 + memo[mask]);
else memo[mask | p] = max(memo[mask | p], memo[mask]);
if(not vis[new_sum]){
vis[new_sum] = true;
Q.emplace(new_sum);
}
}
}
return *max_element(memo, memo + (1 << m)) == n;
}
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);
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... |