Submission #1155970

#TimeUsernameProblemLanguageResultExecution timeMemory
1155970onbertCookies (JOI23_cookies)C++20
6 / 100
2 ms1220 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5, INF = 1e9;
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n;
    pair<int,int> a[n+1];
    for (int i=1;i<=n;i++) {cin >> a[i].first, a[i].second = i;}
    cin >> m;
    int b[m];
    for (int i=0;i<m;i++) cin >> b[i];

    sort(a+1, a+n+1);
    int mx = a[n].first;
    int freq[mx+2];
    for (int i=0;i<=mx+1;i++) freq[i] = 0;
    for (int i=1;i<=n;i++) freq[a[i].first]++;
    for (int i=mx;i>=1;i--) freq[i] += freq[i+1];
    vector<pair<int,int>> vec = {{0, 0}};
    for (int i=mx;i>=1;i--) {
        for (int j=1;j<=freq[i];j++) vec.push_back({a[n - freq[i] + j].second, min(freq[i+1]+j, freq[i])});
    }
    int sz = vec.size();
    // for (auto [x, y]:vec) cout << x << "." << y << " "; cout << endl;
    pair<int,int> dp[sz];
    for (int i=0;i<sz;i++) dp[i] = {INF, -1};
    dp[0] = {0, -1};
    for (int i=1;i<sz;i++) {
        for (int j:b) if (i - j >= 0 && j <= vec[i].second) {
            dp[i] = min(make_pair(dp[i-j].first+1, i - j), dp[i]);
        }
        // cout << i << " " << vec[i].second << " " << dp[i].first << " " << dp[i].second << endl;
    }
    // return 0;
    if (dp[sz-1].first == INF) cout << "-1\n";
    else {
        cout << dp[sz-1].first << "\n";
        int u = sz-1;
        while (u != 0) {
            int v = dp[u].second;
            cout << u - v << " ";
            while (u > v) {
                cout << vec[u].first << " ";
                u--;
            }
            cout << "\n";
            u = v;
        }
    }
}
#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...