Submission #591398

#	Time	Username	Problem	Language	Result	Execution time	Memory
591398		kshitij_sodani	Packing Biscuits (IOI20_biscuits)	C++14	100 / 100	21 ms	1332 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
 
#include "biscuits.h"
llo ans[2000001];
llo dp[61];
llo dp2[61];
llo xx2[61];
long long count_tastiness(long long x, vector<long long> it) {
	while(it.size()<60){
		it.pb(0);
	}
	llo su=0;
//	ans[0]=0;
	//llo cc=1;
	for(int i=0;i<it.size();i++){
		su+=(1LL<<i)*it[i];
		llo xx=su/x;
		xx-=(1LL<<i);
		xx=min(xx,(1LL<<i)-1);
		xx2[i]=xx;
		if(xx<0){
			dp[i]=0;
			dp2[i+1]=dp2[i];
			continue;
		}
		dp[i]=1;
		vector<int> ss;
		for(int j=i-1;j>=0;j--){
			if((1LL<<j)&xx){
				ss.pb(j);
			}
		}
		llo cur=xx;
		for(int j=0;j<ss.size();j++){
			dp[i]+=dp2[ss[j]];
			if(xx2[ss[j]]<0){
				break;
			}
			cur-=(1LL<<ss[j]);
			if(xx2[ss[j]]<=cur){
				dp[i]+=dp[ss[j]];
				break;
			}
			else{
				dp[i]+=1;
			}
		}
		dp2[i+1]=dp2[i]+dp[i];
	}
 
 
 
 
	return dp2[it.size()]+1;
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<it.size();i++){
      |              ~^~~~~~~~~~
biscuits.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int j=0;j<ss.size();j++){
      |               ~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23