제출 #1351503

#제출 시각아이디문제언어결과실행 시간메모리
1351503alexddCookies (JOI23_cookies)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 505;

bitset<MAXN> dp[MAXN][MAXN];
int n, m;
int a[MAXN], b[MAXN];


signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    int tot = 0, mxm = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        tot += a[i];
        mxm = max(mxm, a[i]);
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }

    dp[0][0][0] = 1;
    for(int i=1;i<=m;i++)
    {
        for(int cnt=0;cnt<=m;cnt++)
            dp[i][cnt] = dp[i-1][cnt];
        for(int cnt=1;cnt<=m;cnt++)
            dp[i][cnt] = (dp[i][cnt] | (dp[i][cnt-1]<<b[i]));
    }

    int unde = -1;
    for(int cnt=mxm;cnt<=m;cnt++)
    {
        if(dp[m][cnt][tot])
        {
            unde = cnt;
            break;
        }
    }
    if(unde == -1)
    {
        cout<<-1;
        return 0;
    }

    cout<<unde<<"\n";
    for(int pas=m;pas>=1;pas--)
    {
        if(dp[pas-1][unde][tot])
            continue;

        bool gasit = 0;
        for(int cate=1;cate*b[pas]<=tot && cate<=unde;cate++)
        {
            if(dp[pas-1][unde-cate][tot-cate*b[pas]])
            {
                for(int _=0;_<cate;_++)
                {
                    cout<<b[pas]<<" ";
                    vector<pair<int,int>> ord;
                    for(int i=1;i<=n;i++)
                        ord.push_back({a[i], i});
                    sort(ord.begin(), ord.end());
                    reverse(ord.begin(), ord.end());
                    for(int i=0;i<b[pas];i++)
                    {
                        int x = ord[i].second;
                        cout<<x<<" ";
                        a[x]--;
                    }
                    cout<<"\n";
                }
                unde -= cate;
                tot -= cate * b[pas];
                gasit = 1;
                break;
            }
        }
        assert(gasit);
    }

    return 0;
}
/*
*/
#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...