| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1146537 | mychecksedad | Cookies (JOI23_cookies) | C++20 | 0 ms | 0 KiB |
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 3000+100, M = 1e5+10, K = 52, MX = 30;
struct E{
bool ok;
int go;
};
int n, b[N], m, pref[N];
E DP[N][N];
array<int, 2> a[N];
pair<bool, vector<vi>> f(vector<pii> A){
vector<vi> res(A.size());
for(int i = 1; i <= n; ++i){
if(A.size() < a[i][0]){
return pair<bool, vector<vi>>{false, res};
}
for(int j = 0; j < a[i][0]; ++j){
if(A[j].ff == 0){
return pair<bool, vector<vi>>{false, res};
}
A[j].ff--;
res[A[j].ss].pb(a[i][1]);
}
sort(all(A));
reverse(all(A));
}
return pair<bool, vector<vi>>{true, res};
}
void solve(){
cin >> n;
int s = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i][0];
a[i][1] = i;
s += a[i][0];
}
sort(a+1, a+1+n, greater<array<int, 2>>());
pref[0] = 0;
for(int i = 1; i <= n; ++i){
pref[i] = pref[i - 1] + a[i][0];
}
cin >> m;
vector<bool> is_size(s + 1);
for(int i = 1; i <= m; ++i){
cin >> b[i];
is_size[b[i]] = 1;
}
sort(b+1, b+1+m);
for(int i = 0; i <= s + 1; ++i){
for(int j = 0; j <= s + 1; ++j) DP[i][j] = {0, 0};
}
b[0] = 0;
is_size[0] = 1;
DP[m + 1][0] = {true, 0};
for(int i = m; i >= 1; --i){
int SZ = b[i], LEN = b[i] - b[i - 1];
for(int cur_sum = s; cur_sum >= 0; --cur_sum){
if(!DP[i + 1][cur_sum].ok || s - cur_sum < pref[b[i]]) continue;
for(int x = DP[i + 1][cur_sum].go; x * LEN + sum <= s; ++x){
int next_sum = cur_sum + x * LEN;
bool good = 1;
int k = s - next_sum;
for(int j = b[i-1]; j <= b[i]; ++j){
if(k < pref[j]) good = 0; // precompute it, now go to fuckin sleep
k += x;
// cout << k << ' ' << pref[j] <<'\n';
}
// en;
if(good && DP[i][next_sum].ok == false && DP[i + 1][cur_sum].ok){
DP[i][next_sum] = {true, x};
}
}
}
}
if(DP[1][s].ok){
vector<pii> boxes;
int cur_num = DP[1][s].go, cur_sum = s;
for(int i = 1; i <= m; ++i){
if(cur_sum == 0) break;
int LEN = b[i] - b[i - 1];
auto dp = DP[i + 1][cur_sum - cur_num * LEN];
if(cur_num > dp.go){
for(int l = dp.go; l < cur_num; ++l) boxes.pb({b[i], boxes.size()});
}
cur_sum -= cur_num * LEN;
cur_num = dp.go;
}
assert(cur_sum == 0);
sort(all(boxes), greater<pii>());
auto g = f(boxes);
assert(g.ff);
cout << g.ss.size() << '\n';
for(auto v: g.ss){
cout << v.size() << ' ';
for(int u: v) cout << u << ' ';
en;
}
return;
}
cout << -1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}