Submission #1154935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154935		tosivanmak	Cookies (JOI23_cookies)	C++20	0 / 100	14 ms	27980 KiB

cookies

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

ll suff[15002],pref[15002];
ll n;
bitset<15002>dp[15002];
bitset<15002>xo[15002];
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);
    cin>>n;
    ll a[n+5];
    xo[0][0]=1;
    for(int i=1;i<=15000;i++){
        xo[i]=xo[i-1]; xo[i][i]=1;
    }
    dp[0][0]=1;
    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];
    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];
            dp[k+1]|=((dp[k]&xo[p])<<b[i]);
        }
    }
    ll x=sum,y=-1;
    for(int i=0;i<=sum;i++){
        if(dp[i][sum]){
            cout<<i<<'\n'; y=i; break;
        }
    }
    if(y==-1){
        cout<<y<<'\n'; return 0;
    }
    vector<ll>rec;
    ll noww=sum;
    for(int i=y;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(dp[i-1][noww-j]){
                rec.push_back(j); noww-=j;
                break;
            }
        }
    }
    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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 45
• Subtask 5: 0 / 15
• Subtask 6: 0 / 15