Submission #857537

#TimeUsernameProblemLanguageResultExecution timeMemory
857537willychanCookies (JOI23_cookies)C++14
7 / 100
35 ms76404 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; //#include<bits/extc++.h> //__gnu_pbds vector<pair<int,int> > a; vector<int> b; const int N = 15005; vector<bitset<N> > req; vector<int> pa(N); vector<bitset<N>> dp[N]; int n; int m; void printb(bitset<N> &k){ cout<<"printing: "; for(int i=0;i<=pa[n];i++){ cout<<k[i]; } cout<<"\n"; } void cons(pair<int,int> cur,int val,vector<int> &result){ int i = cur.first; int j = cur.second; result.push_back(i); j--; if(j==0) return; if(dp[i][j][val-b[i]]) cons({i,j},val-b[i],result); else cons({i-1,j},val-b[i],result); } int main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; a.resize(n+1); for(int i=1;i<=n;i++){ cin>>a[i].first;a[i].second=i;} cin>>m; b.resize(m+1); for(int i=1;i<=m;i++) cin>>b[i]; sort(b.begin()+1,b.end(),greater<int>()); sort(a.begin()+1,a.end()); for(int i=1;i<=n;i++) pa[i] = pa[i-1]+a[i].first; int head =1; int cur=0; bitset<N> reqnow; req.push_back(reqnow); for(int i=1;i<=N;i++){ while(head<=n && a[head].first<=i){ head++; } while(cur<N && cur<=pa[head-1]+(i*(n-head+1))){ reqnow[cur]=1; cur++; } req.push_back(reqnow); } for(int i=1;i<=m;i++){ int J = min(pa[n],(pa[n]/b[i])+1); bitset<N> s; dp[i].push_back(s); dp[i][0][0]=1; for(int j=1;j<=J;j++){ s.reset(); s|=((dp[i][j-1])<<b[i]); if(dp[i-1].size()>j-1) s|=(dp[i-1][j-1]<<b[i]); s&=req[j]; dp[i].push_back(s); } } pair<int,int> works; for(int j=1;j<=pa[n];j++){ if(works.first) break; for(int i=m;i>=1;i--){ if(works.first) break; if(j>=dp[i].size()) break; if(dp[i][j][pa[n]]){ works = {i,j}; break; } } } if(!works.first){ cout<<-1<<"\n"; return 0; } cout<<works.second<<"\n"; vector<int> result; cons(works,pa[n],result); for(int i=0;i<result.size();i++){ result[i] = b[result[i]]; } sort(result.begin(),result.end(),greater<int>()); priority_queue<pair<int,int> > pq; for(int i=1;i<=n;i++) pq.push(a[i]); for(auto g : result){ vector<int> ans; vector<pair<int,int> > goback; for(int a=0;a<g;a++){ pair<int,int> temp = pq.top(); pq.pop(); ans.push_back(temp.second); temp.first--; if(temp.first) goback.push_back(temp); } cout<<g<<" "; for(int i=0;i<ans.size();i++) cout<<ans[i]<<" "; cout<<"\n"; for(auto temp : goback) pq.push(temp); } return 0; }

Compilation message (stderr)

cookies.cpp: In function 'int main()':
cookies.cpp:68:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |    if(dp[i-1].size()>j-1) s|=(dp[i-1][j-1]<<b[i]);
      |       ~~~~~~~~~~~~~~^~~~
cookies.cpp:78:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::bitset<15005> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    if(j>=dp[i].size()) break;
      |       ~^~~~~~~~~~~~~~
cookies.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i=0;i<result.size();i++){
      |              ~^~~~~~~~~~~~~~
cookies.cpp:110:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
      |               ~^~~~~~~~~~~
#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...