QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #612 | #392200 | #7403. Subset Sum | 5sb | iee | Success! | 2024-05-04 13:41:30 | 2024-05-04 13:41:31 |
详细
Extra Test:
Wrong Answer
time: 1010ms
memory: 4380kb
input:
1 20000 200000000 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 ...
output:
199999903
result:
wrong answer 1st numbers differ - expected: '200000000', found: '199999903'
| 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;
}