Submission #1035988

#TimeUsernameProblemLanguageResultExecution timeMemory
1035988tvladm2009Cookies (JOI23_cookies)C++17
85 / 100
1069 ms515696 KiB
#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)

cookies.cpp: In function 'int main()':
cookies.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                     if (j == boxes.size()) {
      |                         ~~^~~~~~~~~~~~~~~
cookies.cpp:111:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for (int i = 0; i < boxes.size(); ++i) {
      |                             ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...