QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #637 | #405203 | #7403. Subset Sum | 5sb | iee | Failed. | 2024-05-24 18:14:10 | 2024-05-24 18:14:10 |
详细
Extra Test:
Accepted
time: 1887ms
memory: 4936kb
input:
2 10000 99995000 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:
99995000 100000000
result:
ok 2 number(s): "99995000 100000000"
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #405203 | #7403. Subset Sum | iee | WA | 1885ms | 5200kb | C++14 | 763b | 2024-05-05 13:41:30 | 2024-05-24 18:17:35 |
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;
}
static mt19937 eng(chrono::steady_clock::now().time_since_epoch().count());
sort(a.rbegin(), a.rend());
int w = 0;
for (int &x : a) {
if (x <= c) {
c -= x;
w += x;
x *= -1;
}
}
constexpr int N = 1.8e6 + 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;
}