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>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 3030
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int A[MAX];
int cnt[MAX];
int B[MAX];
int dp[MAX][MAX];
vector<int> ansv;
int N, M;
int bdp[MAX];
void print() {
vector<int> v;
vector<vector<int>> res;
int i;
for (i = 1; i <= N; i++) v.push_back(i);
for (auto b : ansv) {
vector<int> nv;
sort(v.begin(), v.end(), [&](int i, int j) {return A[i] > A[j]; });
for (i = 0; i < b; i++) {
nv.push_back(v[i]);
A[v[i]]--;
}
res.push_back(nv);
}
for (i = 1; i <= N; i++) if (A[i]) {
cout << -1 << ln;
exit(0);
}
cout << res.size() << ln;
for (auto& v : res) {
cout << v.size() << bb;
for (auto x : v) cout << x << bb;
cout << ln;
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N;
int i, j, k;
int S = 0;
for (i = 1; i <= N; i++) {
cin >> A[i];
S += A[i];
for (j = 1; j <= A[i]; j++) cnt[j]++;
}
cin >> M;
for (i = 1; i <= M; i++) cin >> B[i];
if (M == 1) {
if (S % B[1]) {
cout << -1 << ln;
return 0;
}
ansv = vector<int>(S / B[1], B[1]);
print();
return 0;
}
for (i = 1; i <= S; i++) cnt[i] += cnt[i - 1];
memset(dp, -1, sizeof(dp));
dp[0][0] = 1e9;
for (i = 1; i <= S; i++) {
for (j = 0; j <= cnt[i - 1]; j++) {
if (!~dp[i - 1][j]) continue;
for (k = 1; k <= M && B[k] * i <= S; k++) if (j + B[k] <= cnt[i] && B[k] <= dp[i - 1][j]) dp[i][j + B[k]] = max(dp[i][j + B[k]], B[k]);
}
}
int loc;
for (i = 1; i <= S; i++) if (~dp[i][S]) break;
loc = i;
if (loc > S) {
cout << -1;
return 0;
}
int n = S;
for (i = loc; i >= 1; i--) {
int path = dp[i][n];
assert(path != -1);
n -= path;
if (path) ansv.push_back(path);
}
sort(ansv.begin(), ansv.end(), [&](int i, int j) {return i > j; });
print();
}
# | 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... |