Submission #804508

#	Time	Username	Problem	Language	Result	Execution time	Memory
804508		mousebeaver	Cookies (JOI23_cookies)	C++14	6 / 100	1 ms	340 KiB

cookies

#define ll long long
#define INF numeric_limits<ll>::max()/2
#define pll pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i = 0; i < n; i++)
    {
        cin>>a[i];
    }
    ll m;
    cin>>m;
    vector<ll> b(m);
    for(ll i = 0; i < m; i++)
    {
        cin>>b[i];
    }

    //Subtask 1:
    vector<pll> dp(n+1, {INF, -1}); //Number, last
    dp[0] = {0, 0};
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < m && i+b[j] <= n; j++)
        {
            if(dp[i].first+1 < dp[i+b[j]].first)
            {
                dp[i+b[j]].first = dp[i].first+1;
                dp[i+b[j]].second = j;
            }
        }
    }

    if(dp[n].first == INF)
    {
        cout<<-1<<"\n";
    }
    else
    {
        cout<<dp[n].first<<"\n";
        ll k = n;
        ll counter = 1;
        while(k > 0)
        {
            ll box = b[dp[k].second];
            k -= box;
            cout<<box<<" ";
            while(box > 0)
            {
                cout<<counter<<" ";
                counter++;
                box--;
            }
            cout<<"\n";
        }
    }

    return 0;  
}

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