이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n, m;
int salary[N], notes[N], pref[N+1];
int dp[1 << N], sum[1 << N];
signed main(){
cin >> n >> m;
int cur_pref = 0;
pref[0] = 0;
for(int i = 0; i < n; i++){
cin >> salary[i];
//cur_pref += salary[i];
pref[i+1] = pref[i] + salary[i];
}
for(int i = 0; i < m; i++){
cin >> notes[i];
}
for(int i = 0; i < (1 << m); i++){
int cur = 0;
for(int j = 0; j < m; j++){
if(i & (1 << j)) cur += notes[j];
}
sum[i] = cur;
}
vector<int> masks[N];
for(int i = 0; i < (1 << m); i++)
masks[__builtin_popcount(i)].push_back(i);
memset(dp, 0, sizeof dp);
dp[0] = true;
for(int i = 0; i < m; i++){
for(int mask: masks[i]){
for(int j = 0; j < m; j++){
if((mask & (1 << j)) || !dp[mask]) continue;
int nmask = mask | (1 << j);
auto lb1 = upper_bound(pref, pref+n, sum[mask]);
auto lb2 = upper_bound(pref, pref+n, sum[nmask]);
lb1--, lb2--;
if(lb1 != lb2){
if(lb2 == next(lb1) && *lb2 == sum[nmask])
dp[nmask] = true;
} else{
dp[nmask] = true;
}
}
//cout << bitset<6>(mask) << " " << dp[mask] << endl;
}
}
bool ans = false;
for(int mask = 0; mask < (1 << m); mask++){
if(sum[mask] == pref[n]){
//printf("mask %d has sum equals %d, dp = %d\n", mask, pref[n], dp[mask]);
}
if(sum[mask] == pref[n] && dp[mask])
ans = true;
}
if(ans)
cout << "YES";
else
cout << "NO";
}
컴파일 시 표준 에러 (stderr) 메시지
bank.cpp: In function 'int main()':
bank.cpp:11:7: warning: unused variable 'cur_pref' [-Wunused-variable]
11 | int cur_pref = 0;
| ^~~~~~~~
# | 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... |