oj.uz

Submission #857537

# Submission time Handle Problem Language Result Execution time Memory
857537 2023-10-06T10:54:41 Z willychan Cookies (JOI23_cookies) C++14
7 / 100
 35 ms 76404 KB 
#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

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]<<" ";
      |               ~^~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32524 KB Output is correct
2 Correct 12 ms 33036 KB Output is correct
3 Correct 14 ms 32268 KB Output is correct
4 Correct 12 ms 33028 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 13 ms 32008 KB Output is correct
7 Correct 11 ms 32524 KB Output is correct
8 Correct 13 ms 33036 KB Output is correct
9 Correct 12 ms 33032 KB Output is correct
10 Correct 19 ms 39544 KB Output is correct
11 Correct 17 ms 32012 KB Output is correct
12 Correct 15 ms 33604 KB Output is correct
13 Correct 13 ms 32084 KB Output is correct
14 Correct 14 ms 32268 KB Output is correct
15 Correct 13 ms 33036 KB Output is correct
16 Correct 13 ms 31952 KB Output is correct
17 Correct 12 ms 32780 KB Output is correct
18 Incorrect 12 ms 31500 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32268 KB Output is correct
2 Correct 13 ms 31788 KB Output is correct
3 Correct 12 ms 33036 KB Output is correct
4 Correct 11 ms 33036 KB Output is correct
5 Correct 13 ms 31416 KB Output is correct
6 Correct 11 ms 31012 KB Output is correct
7 Correct 13 ms 31500 KB Output is correct
8 Correct 13 ms 32076 KB Output is correct
9 Correct 19 ms 43636 KB Output is correct
10 Correct 35 ms 76404 KB Output is correct
11 Correct 12 ms 32012 KB Output is correct
12 Correct 11 ms 32780 KB Output is correct
13 Correct 12 ms 30988 KB Output is correct
14 Correct 12 ms 31060 KB Output is correct
15 Correct 12 ms 31440 KB Output is correct
16 Correct 14 ms 31556 KB Output is correct
17 Correct 12 ms 32776 KB Output is correct
18 Correct 20 ms 43592 KB Output is correct
19 Correct 25 ms 54856 KB Output is correct
20 Correct 16 ms 32264 KB Output is correct
21 Correct 13 ms 31496 KB Output is correct
22 Correct 13 ms 33036 KB Output is correct
23 Correct 12 ms 32268 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32012 KB Output is correct
2 Correct 14 ms 31500 KB Output is correct
3 Correct 13 ms 33036 KB Output is correct
4 Correct 12 ms 31736 KB Output is correct
5 Correct 11 ms 33036 KB Output is correct
6 Correct 11 ms 31496 KB Output is correct
7 Correct 11 ms 32012 KB Output is correct
8 Correct 12 ms 31256 KB Output is correct
9 Correct 12 ms 32012 KB Output is correct
10 Correct 12 ms 32720 KB Output is correct
11 Correct 12 ms 31500 KB Output is correct
12 Correct 13 ms 33032 KB Output is correct
13 Correct 13 ms 32912 KB Output is correct
14 Correct 11 ms 32264 KB Output is correct
15 Correct 12 ms 32012 KB Output is correct
16 Correct 11 ms 31240 KB Output is correct
17 Correct 13 ms 31756 KB Output is correct
18 Correct 12 ms 32012 KB Output is correct
19 Correct 11 ms 32268 KB Output is correct
20 Correct 11 ms 32860 KB Output is correct
21 Correct 11 ms 32536 KB Output is correct
22 Correct 11 ms 32524 KB Output is correct
23 Correct 12 ms 31752 KB Output is correct
24 Correct 12 ms 32524 KB Output is correct
25 Correct 11 ms 32780 KB Output is correct
26 Correct 11 ms 31764 KB Output is correct
27 Correct 13 ms 31768 KB Output is correct
28 Correct 13 ms 31000 KB Output is correct
29 Correct 11 ms 32772 KB Output is correct
30 Correct 11 ms 32792 KB Output is correct
31 Incorrect 11 ms 31260 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32524 KB Output is correct
2 Correct 12 ms 33036 KB Output is correct
3 Correct 14 ms 32268 KB Output is correct
4 Correct 12 ms 33028 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 13 ms 32008 KB Output is correct
7 Correct 11 ms 32524 KB Output is correct
8 Correct 13 ms 33036 KB Output is correct
9 Correct 12 ms 33032 KB Output is correct
10 Correct 19 ms 39544 KB Output is correct
11 Correct 17 ms 32012 KB Output is correct
12 Correct 15 ms 33604 KB Output is correct
13 Correct 13 ms 32084 KB Output is correct
14 Correct 14 ms 32268 KB Output is correct
15 Correct 13 ms 33036 KB Output is correct
16 Correct 13 ms 31952 KB Output is correct
17 Correct 12 ms 32780 KB Output is correct
18 Incorrect 12 ms 31500 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32524 KB Output is correct
2 Correct 12 ms 33036 KB Output is correct
3 Correct 14 ms 32268 KB Output is correct
4 Correct 12 ms 33028 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 13 ms 32008 KB Output is correct
7 Correct 11 ms 32524 KB Output is correct
8 Correct 13 ms 33036 KB Output is correct
9 Correct 12 ms 33032 KB Output is correct
10 Correct 19 ms 39544 KB Output is correct
11 Correct 17 ms 32012 KB Output is correct
12 Correct 15 ms 33604 KB Output is correct
13 Correct 13 ms 32084 KB Output is correct
14 Correct 14 ms 32268 KB Output is correct
15 Correct 13 ms 33036 KB Output is correct
16 Correct 13 ms 31952 KB Output is correct
17 Correct 12 ms 32780 KB Output is correct
18 Incorrect 12 ms 31500 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32524 KB Output is correct
2 Correct 12 ms 33036 KB Output is correct
3 Correct 14 ms 32268 KB Output is correct
4 Correct 12 ms 33028 KB Output is correct
5 Correct 13 ms 31748 KB Output is correct
6 Correct 13 ms 32008 KB Output is correct
7 Correct 11 ms 32524 KB Output is correct
8 Correct 13 ms 33036 KB Output is correct
9 Correct 12 ms 33032 KB Output is correct
10 Correct 19 ms 39544 KB Output is correct
11 Correct 17 ms 32012 KB Output is correct
12 Correct 15 ms 33604 KB Output is correct
13 Correct 13 ms 32084 KB Output is correct
14 Correct 14 ms 32268 KB Output is correct
15 Correct 13 ms 33036 KB Output is correct
16 Correct 13 ms 31952 KB Output is correct
17 Correct 12 ms 32780 KB Output is correct
18 Incorrect 12 ms 31500 KB Output isn't correct
19 Halted 0 ms 0 KB -