# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1035988 | tvladm2009 | Cookies (JOI23_cookies) | C++17 | 1069 ms | 515696 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3000 + 7;
const int M = 15000 + 7;
int n, m, a[M], b[M];
int vertical[M];
struct MyBitset {
vector<ll> b;
int n;
void resize(int nn) {
n = nn;
b.resize(n / 63 + 2, 0);
}
void set(int x) {
b[x / 63] |= (1LL << (x % 63));
}
bool get(int x) {
if (x > n) {
return 0;
}
if (b[x / 63] & (1LL << (x % 63))) {
return true;
} else {
return false;
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
cin >> m;
for (int i = 1; i <= m; ++i) cin >> b[i];
int sumA = 0;
for (int i = 1; i <= n; ++i) {
sumA += a[i];
}
reverse(b + 1, b + m + 1);
for (int i = 1; i <= sumA; ++i) {
for (int j = 1; j <= n; ++j) {
vertical[i] += min(i, a[j]);
}
}
vector<vector<MyBitset>> dp(m + 1, vector<MyBitset>(sumA + 1));
dp[0][0].resize(1);
dp[0][0].set(0);
for (int i = 1; i <= m; ++i) {
for (int sum = 0; sum <= sumA; ++sum) {
dp[i][sum].resize(sum / b[i]);
}
for (int sum = 0; sum <= sumA; ++sum) {
for (int x = 0; x <= sum / b[i]; ++x) {
if (vertical[x] >= sum) {
bool b1 = (x == 0 ? 0 : dp[i][sum - b[i]].get(x - 1));
bool b2 = dp[i - 1][sum].get(x);
if (b1 | b2) {
dp[i][sum].set(x);
}
// dp[i][sum][x] = dp[i][x - 1][sum - b[i]] | dp[i - 1][x][sum];
}
}
}
}
for (int x = 1; x <= sumA / b[m]; ++x) {
if (dp[m][sumA].get(x) == true) {
cout << x << "\n";
vector<pair<int, int>> boxes;
int cnt = x;
int sum = sumA;
int pos = m;
while (pos > 0) {
if (cnt != 0 && dp[pos][sum - b[pos]].get(cnt - 1)) {
boxes.push_back({b[pos], boxes.size()});
sum -= b[pos];
cnt--;
} else {
assert(dp[pos - 1][sum].get(cnt) == 1);
pos--;
}
}
vector<vector<int>> sol(boxes.size());
for (int i = 1; i <= n; ++i) {
sort(boxes.rbegin(), boxes.rend());
int j = 0;
while (a[i] > 0) {
if (j == boxes.size()) {
cout << i << "\n";
return 0;
}
if (boxes[j].first > 0) {
sol[boxes[j].second].push_back(i);
boxes[j].first--;
a[i]--;
}
j++;
}
}
for (int i = 0; i < boxes.size(); ++i) {
cout << sol[i].size() << " ";
for (auto j : sol[i]) {
cout << j << " ";
}
cout << "\n";
}
return 0;
}
}
cout << -1 << "\n";
return 0;
}
Compilation message (stderr)
# | 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... |