QOJ.ac
QOJ
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #638 | #405203 | #7403. Subset Sum | 5sb | iee | Success! | 2024-05-24 18:14:47 | 2024-05-24 18:14:47 |
詳細信息
Extra Test:
Wrong Answer
time: 1883ms
memory: 5016kb
input:
1 20000 199990000 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:
199980000
result:
wrong answer 1st numbers differ - expected: '199990000', found: '199980000'
| 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;
}