Submission #332194

#	Time	Username	Problem	Language	Result	Execution time	Memory
332194		pggp	Packing Biscuits (IOI20_biscuits)	C++14	42 / 100	1080 ms	768 KiB

biscuits

#include <bits/stdc++.h>

using namespace std;

long long count_tastiness(long long x, vector < long long > k){
	if(x <= 10000){
		k.resize(62);
		for (long long i = 0; i < k.size() - 1; ++i)
		{
			if(k[i] > x){
				k[i + 1] += (k[i] - x)/2;
				k[i] -= 2 * ((k[i] - x)/2);
			}
			//cout << "k: " << k[i] << endl;
		}
		long long DP[2 * x + 2];
		long long DP1[2 * x + 2];
		for (long long j = 0; j < 2 * x + 2; ++j)
		{
			DP[j] = DP1[j] = 0; 
		}
		DP[k[0]] = 1;
		for (long long i = 0; i < k.size() - 1; ++i)
		{
			// używamy x
			for (long long j = 0; j < 2 * x + 2 and k[i + 1] + (j - x) / 2 < 2 * x + 2; ++j)
			{
				if(j >= x){
					DP1[k[i + 1] + (j - x) / 2] += DP[j]; 
				}
			}

			// nie używamy x

			for (long long j = 0; j < 2 * x + 2 and k[i + 1] + j / 2 < 2 * x + 2; ++j)
			{
				DP1[k[i + 1] + j / 2] += DP[j]; 
			}

			for (long long j = 0; j < 2 * x + 2; ++j)
			{
				//cout << DP1[j] << " "; 
			}

			for (long long j = 0; j < 2 * x + 2; ++j)
			{
				DP[j] = DP1[j]; 
				DP1[j] = 0;
			}

			
			//cout << endl;
		}

		long long sum = 0;
		for (long long i = 0; i < 2 * x + 1; ++i)
		{
			sum += DP[i];
		}
		return sum;
	}
	else{
		long long total_tastiness = 0;
		long long cur_pow = 1;
		k.resize(62);
		for (int i = 0; i < k.size(); ++i)
		{
			total_tastiness += cur_pow * k[i];
			cur_pow *= 2;
		}

		int ans = 1;
		long long k_cur;
		for(int y = 1; y <= total_tastiness; y++){
			int y_cur = y;
			int y_dig = 0;
			bool possible = true;
			k_cur = k[0];
			while(y_cur > 0){
				//cout << "y_cur:" <<  y_cur << endl;
				//cout << "k_cur:" <<  k_cur << endl;
				if(y_cur % 2 == 1){
					k_cur -= x;
					if(k_cur < 0){
						possible = false;
					}
				}
				k_cur /= 2;
				k_cur += k[y_dig + 1];
				y_dig++;
				y_cur /= 2;
			}
			if(possible){
				//cout << "p: " << y << endl;
			}
			ans += possible;
		}


		return ans;
	}
	
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:8:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |   for (long long i = 0; i < k.size() - 1; ++i)
      |                         ~~^~~~~~~~~~~~~~
biscuits.cpp:23:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (long long i = 0; i < k.size() - 1; ++i)
      |                         ~~^~~~~~~~~~~~~~
biscuits.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 0; i < k.size(); ++i)
      |                   ~~^~~~~~~~~~

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