이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int maxc = 20000 + 1;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int& i : a) cin >> i;
for (int& i : b) cin >> i;
random_device rd;
mt19937 g(rd());
shuffle(a.begin(), a.end(), g);
shuffle(b.begin(), b.end(), g);
vector<int> pr(n + 1);
for (int i = 0; i < n; ++i) {
pr[i + 1] = pr[i] + a[i];
}
vector<int> summask((1 << m));
for (int mask = 0; mask < (1 << m); ++mask) {
for (int i = 0; i < m; ++i) {
if ((mask & (1 << i))) {
summask[mask] += b[i];
}
}
}
vector<int> needmask = { 0 };
vector<vector<int>> dp(n, vector<int>(1 << m));
vector<vector<int>> posmask(n + 1);
for (int mask = 0; mask < (1 << m); ++mask) {
for (int i = 0; i <= n; ++i) {
if (summask[mask] == pr[i]) posmask[i].push_back(mask);
}
}
for (int i = 0; i < n; ++i) {
int needsum = pr[i];
vector<int> q;
for (int mask : posmask[i + 1]) {
for (auto mask1 : needmask) {
if ((mask & mask1) == mask1) {
dp[i][mask] = 1;
q.push_back(mask);
break;
}
}
}
swap(needmask, q);
}
for (int i = 0; i < (1 << m); ++i) {
if (dp[n - 1][i]) {
cout << "YES";
return 0;
}
}
cout << "NO";
}
컴파일 시 표준 에러 (stderr) 메시지
bank.cpp: In function 'int main()':
bank.cpp:38:13: warning: unused variable 'needsum' [-Wunused-variable]
38 | int needsum = pr[i];
| ^~~~~~~
# | 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... |