제출 #1155970

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155970		onbert	Cookies (JOI23_cookies)	C++20	6 / 100	2 ms	1220 KiB

cookies

#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;
        }
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 45
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15