| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1352088 | Aisha | Uplifting Excursion (BOI22_vault) | C++20 | 5091 ms | 589824 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int m, wt; cin >> m >> wt;
map <int, int> f, mf;
for (int i = -m; i <= m; i ++) {
int x; cin >> x;
if (i < 0) mf[-i] = x;
else f[i] = x;
}
/*
for (auto [i, x] : f) {
if (i == 0) continue;
if (x == 0) continue;
x --; f[i] = 1;
int k = 2;
while (k <= x) {
x -= k;
f[i * k] ++;
k ++;
}
if (x) f[i * x] ++;
}
for (auto [i, x] : mf) {
if (x == 0) continue;
x --; mf[i] = 1;
int k = 2;
while (k <= x) {
x -= k;
mf[i * k] ++;
k ++;
}
if (x) mf[i * x] ++;
}
*/
vector <int> a;
for (auto [i, x] : f) {
if (i == 0) continue;
while (x --) a.push_back(i);
}
for (auto [i, x] : mf) {
while (x --) a.push_back(-i);
}
int n = a.size();
map <int, int> cnt; cnt[-0] = 0;
bool ok = false;
for (int i = 0; i < n; i ++) {
// cout << a[i] << endl;
if (a[i] < 0 && !ok) {
map <int, int> cntc;
for (auto [x, c] : cnt) {
cntc[-x] = c;
}
cnt = cntc;
ok = true;
}
for (auto [x, c] : cnt) {
// cout << x << ' ' << c << endl;
// -x kattadan kichikka qarab
if (!ok) cnt[x - a[i]] = max(cnt[x - a[i]], cnt[x] + 1);
else cnt[x + a[i]] = max(cnt[x + a[i]], cnt[x] + 1);
}
}
if (ok && cnt.find(wt) == cnt.end() || !ok && cnt.find(-wt) == cnt.end()) cout << "impossible" << endl;
else cout << (ok ? cnt[wt] : cnt[-wt]) + f[0] << endl;
return 0;
}| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
