QOJ.ac
QOJ
| ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
|---|---|---|---|---|---|---|---|
| #593 | #364211 | #7403. Subset Sum | 5sb | iee | Success! | 2024-04-10 20:33:42 | 2024-04-10 20:33:43 |
Details
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 | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #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;
}