Submission #1221732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221732		noyancanturk	Cookies (JOI23_cookies)	C++20	13 / 100	15 ms	840 KiB

cookies

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

using pii=pair<int,int>;

const int lim=15010;

int a[lim],b[lim];
int bad[lim],past1[lim];
int good[lim],past2[lim];

int main(){
  int n;
  cin>>n;
  int sm=0;
  int mx=0;
  for(int i=0;i<n;i++)cin>>a[i],sm+=a[i],mx=max(mx,a[i]);
  int m;
  cin>>m;
  for(int i=0;i<m;i++)cin>>b[i];
  for(int i=1;i<lim;i++){
    bad[i]=INT_MIN;
    good[i]=INT_MAX;
  }
  for(int i=0;i<sm;i++){
    if(bad[i]!=INT_MIN){
      for(int j=0;j<m;j++){
        if(sm<i+b[j])break;
        if(bad[i+b[j]]<bad[i]+1){
          bad[i+b[j]]=bad[i]+1;
          past1[i+b[j]]=b[j];
        }
        if(good[i]+1<good[i+b[j]]){
          good[i+b[j]]=good[i]+1;
          past2[i+b[j]]=b[j];
        }
      }
    }
  }
  if(good[sm]==INT_MAX){
    cout<<-1;
    return 0;
  }
  vector<pii>totr;
  for(int i=0;i<=sm;i++){
    if(bad[i]!=INT_MIN&&good[sm-i]!=INT_MAX&&mx<=bad[i]+good[sm-i]){
      totr.pb({bad[i]+good[sm-i],i});
    }
  }
  sort(totr.begin(),totr.end());
  auto f=[&](int t,int pr) -> bool {
    vector<int>willdo;
    int ss=totr[t].second;
    while(ss){
      willdo.pb(past1[ss]);
      ss-=past1[ss];
    }
    ss=sm-totr[t].second;
    while(ss){
      willdo.pb(past2[ss]);
      ss-=past2[ss];
    }
    int b[n];
    for(int i=0;i<n;i++)b[i]=a[i];
    priority_queue<pii>pq;
    for(int i=0;i<n;i++)pq.push({b[i],i});
    for(int sz:willdo){
      if(pr)cout<<sz<<' ';
      vector<int>used;
      while(sz--){
        auto[x,y]=pq.top();
        pq.pop();
        if(pr)cout<<y+1<<' ';
        used.pb(y);
        b[y]--;
      }
      if(pr)cout<<'\n';
      for(int j:used){
        pq.push({b[j],j});
      }
    }
    for(int i=0;i<n;i++)if(b[i])return 0;
    return 1;
  };
  int l=0,r=totr.size()-1,res=-1;
  while(l<=r){
    int mid=l+r>>1;
    if(f(mid,0)){
      res=mid;
      r=mid-1;
    }else{
      l=mid+1;
    }
  }
  if(res==-1){
    cout<<-1;
    return 0;
  }
  cout<<totr[res].first<<'\n';
  f(res,1);
}

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