QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #593 | #364211 | #7403. Subset Sum | 5sb | iee | Success! | 2024-04-10 20:33:42 | 2024-04-10 20:33:43 |
詳細信息
Extra Test:
Wrong Answer
time: 358ms
memory: 3948kb
input:
40 500 5000000 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 199...
output:
4999998 5000000 5000000 5000000 5000000 5000000 4999994 4999993 5000000 4999999 4999998 5000000 4999996 5000000 4999991 4999996 5000000 5000000 5000000 4999987 5000000 4999996 5000000 5000000 5000000 5000000 5000000 5000000 4999999 4999998 5000000 4999986 4999991 4999998 4999992 4999997 4999999 4999...
result:
wrong answer 1st numbers differ - expected: '5000000', found: '4999998'
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #364211 | #7403. Subset Sum | iee | WA | 364ms | 4220kb | C++23 | 759b | 2024-03-24 13:02:20 | 2024-04-10 20:34:13 |
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 = 4e5 + 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;
}