제출 #1154898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154898		tosivanmak	Cookies (JOI23_cookies)	C++20	78 / 100	1125 ms	881972 KiB

cookies

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2","sse4")
#include<bits/stdc++.h>
using namespace std;
#define ll long long

vector<int>v;
ll suff[15002];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for(int i=0;i<15001;i++)v.push_back(-1);
    vector<vector<int> >rev(15001,v);
    rev[0][0]=0;
    ll n;
    cin>>n;
    ll a[n+5];
    priority_queue<pair<ll,ll> >pts;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        pts.push({a[i],i});
    }
    ll sum=0;
    for(int i=1;i<=n;i++)sum+=a[i];
    sort(a+1,a+n+1); reverse(a+1,a+n+1);
    ll pref[n+5];
    pref[0]=0;
    for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i];
    for(int i=1;i<=n;i++)pref[i]=sum-pref[i];
    pref[n+1]=-1e18;
    for(int i=sum;i>=1;i--){
        ll an;
        for(int j=n;j>=1;j--){
            // pref[i] = canredu[i] + i * j 
            if(j==n) an=pref[j]+i*j;
            else{
                an=min(pref[j]+i*j,an);
            }
        }
        suff[i]=an;
    }
    ll m;
    cin>>m;
    ll b[m+5];
    for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=m;i>=1;i--){
        int s=min(sum-1,sum/b[i]);
        for(int k=0;k<=s;k++){
            int p=min(sum,suff[k+1])-b[i];
            for(int j=0;j<=p;j++){
                if(rev[j][k]==-1)continue;
                if(rev[j+b[i]][k+1]!=-1)continue;
                rev[j+b[i]][k+1]=j;
            }
        }
    }
    ll x=sum,y=-1;
    for(int i=0;i<=sum;i++){
        if(rev[sum][i]!=-1){
            cout<<i<<'\n'; y=i; break;
        }
    }
    if(y==-1){
        cout<<y<<'\n'; return 0;
    }
    vector<ll>rec;
    while(x!=0){
        ll nxtx=rev[x][y],nxty=y-1;
        rec.push_back(x-nxtx);
        x=nxtx; y=nxty;
    }
    sort(rec.rbegin(),rec.rend());
    vector<vector<ll> >ans;
    for(int i=0;i<rec.size();i++){
        vector<pair<ll,ll> >fornxt;
        vector<ll>reco;
        for(int j=1;j<=rec[i];j++){
            pair<ll,ll>cur=pts.top(); pts.pop();
            assert(cur.first!=0);
            fornxt.push_back({cur.first-1,cur.second});
            reco.push_back(cur.second);
        }
        ans.push_back(reco);
        for(auto& u: fornxt)pts.push(u);
    }
    for(auto& u: ans){
        cout<<u.size()<<' ';
        for(auto& v: u){
            cout<<v<<" ";
        }
        cout<<'\n';
    }
}

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