제출 #1347373

#제출 시각아이디문제언어결과실행 시간메모리
1347373MMihalevCookies (JOI23_cookies)C++20
78 / 100
73 ms8904 KiB
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<bitset>
#include<unordered_map>
#include<map>
using namespace std;
const int MAX_N=3003;

int n,m;
int a[MAX_N];
int b[MAX_N];

bitset<MAX_N>bor[MAX_N];
unordered_map<int,bitset<MAX_N>>dp[MAX_N];
int minsum[MAX_N];

vector<int>boxes[MAX_N];
vector<int>box;
void constructans()
{
    sort(box.rbegin(),box.rend());
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++)s.insert({a[i],i});
    
    int j=0;
    for(int B:box)
    {
        j++;
        vector<int>curbox;
        for(auto [sz,type]:s)curbox.push_back(type);

        for(int i=1;i<=B;i++)
        {
            boxes[j].push_back(curbox.back());
            s.erase({a[curbox.back()]--,curbox.back()});
            if(a[curbox.back()])s.insert({a[curbox.back()],curbox.back()});
            curbox.pop_back();
        }
    }

    cout<<box.size()<<"\n";
    for(int i=1;i<=box.size();i++)
    {
        cout<<boxes[i].size()<<" ";
        for(int x:boxes[i])cout<<x<<" ";
        cout<<"\n";
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        all+=a[i];
    }

    for(int boxes=1;boxes<=all;boxes++)
    {
        for(int i=1;i<=n;i++)
        {
            minsum[boxes]+=min(boxes,a[i]);
        }
    }

    bor[0][0]=1;
    for(int sum=1;sum<=all;sum++)
    {
        bor[sum][sum]=1;
        bor[sum]|=bor[sum-1];
    }

    cin>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
    }
    sort(b+1,b+m+1);
    reverse(b+1,b+m+1);
    
    dp[0][0][0]=1;

    for(int id=1;id<=m;id++)
    {
        for(int boxes=0;boxes<=all;boxes++)
        {
            if(dp[id-1].find(boxes)!=dp[id-1].end() && dp[id-1][boxes].any())
            {
                dp[id][boxes]|=dp[id-1][boxes];
            }

            if(boxes)
            {
                int sm=minsum[boxes]-b[id];
                if(sm>=0)
                {
                    if(dp[id].find(boxes-1)!=dp[id].end() && ((dp[id][boxes-1])&(bor[sm])).any())
                    {
                        dp[id][boxes]|=(((dp[id][boxes-1])&(bor[sm]))<<b[id]);
                    }
                }
            }
            
        }
    }

    int ans=-1;
    for(int boxes=1;boxes<=all;boxes++)
    {
        if(dp[m][boxes][all])
        {
            ans=boxes;
            break;
        }
    }

    if(ans==-1)
    {
        cout<<-1<<"\n";
        return 0;
    }

    int id=m,boxes=ans,sum=all;

    while(boxes)
    {
        if(dp[id][boxes-1][sum-b[id]])
        {
            box.push_back(b[id]);
            boxes--;
            sum-=b[id];
        }
        else id--;
    }

    constructans();

    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...