QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #611 | #392200 | #7403. Subset Sum | 5sb | iee | Success! | 2024-05-04 13:38:04 | 2024-05-04 13:38:04 |
詳細信息
Extra Test:
Wrong Answer
time: 1018ms
memory: 4408kb
input:
10 2000 20000000 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 19999 1...
output:
20000000 19999999 20000000 19999989 20000000 20000000 20000000 20000000 20000000 20000000
result:
wrong answer 2nd numbers differ - expected: '20000000', found: '19999999'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #392200 | #7403. Subset Sum | iee | WA | 1040ms | 4528kb | C++14 | 759b | 2024-04-17 11:16:04 | 2024-05-04 13:43:38 |
answer
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, c;
cin >> n >> c;
vector<int> a(n);
for (int &x : a) {
cin >> x;
}
sort(a.begin(), a.end());
int w = 0;
for (int &x : a) {
if (x <= c) {
c -= x;
w += x;
x *= -1;
}
}
static mt19937 eng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1e6 + 5;
bitset<N + N> f;
f[N] = 1;
shuffle(a.begin(), a.end(), eng);
for (int x : a) {
if (x > 0) f |= f << x;
else f |= f >> -x;
}
c = min(c, N - 1);
for (int i = N + c; ; i--) {
if (f[i]) {
cout << i - N + w << "\n";
return;
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}