QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #611 | #392200 | #7403. Subset Sum | 5sb | iee | Success! | 2024-05-04 13:38:04 | 2024-05-04 13:38:04 |
Details
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 | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}