Submission #1154912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154912		tosivanmak	Cookies (JOI23_cookies)	C++20	78 / 100	1130 ms	882020 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],pref[15002];
ll n;

void cal(ll l, ll r, ll optl, ll optr){
    ll mid=(l+r)>>1;
    ll cur=1e18,pos=-1;
    for(int i=optl;i<=optr;i++){
        ll s=pref[i]+i*mid;
        if(s<cur){
            cur=s; pos=i;
        }
    }
    suff[mid]=cur;
    if(l<mid)cal(l,mid-1,pos,optr);
    if(mid<r)cal(mid+1,r,optl,pos);
}
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;
    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);
    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;
    cal(1,sum,1,n);
    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