Submission #825274

#	Time	Username	Problem	Language	Result	Execution time	Memory
825274		fatemetmhr	비스킷 담기 (IOI20_biscuits)	C++17	100 / 100	74 ms	1364 KiB

biscuits

//  ~ Be Name Khoda ~  //

#include "biscuits.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  5e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  2e18;

ll x, sum[100], a[100];


vector <ll> solve(int i, vector <ll> need){
	vector <ll> av;
	if(i == -1){
		av.resize(int(need.size()) + 1);
		fill(all(av), 1);
		return av;
	}
	for(int j = 0; j < need.size(); j++)
		need[j] = max(need[j], 0ll);
	need.pb(0);
	//cout << i << ' ' << need.size() << ' ' << sum[i] << endl;
	for(auto y : need){
		if(inf / x > (1ll << i) && sum[i] - y >= (1ll << i) * x)
			av.pb(y + (x - a[i]) * (1ll << i));
		else
			av.pb(y - a[i] * (1ll << i));
	}
	av = solve(i - 1, av);
	for(int j = 0; j < int(av.size()) - 1; j++){
		if(inf / x > (1ll << i) && sum[i] - need[j] >= (1ll << i) * x)
			av[j] += av.back();
		//cout << "* " << i << ' ' << j << ' ' << need[j] << ' ' << av[j] << ' ' << endl;
	}
	av.pop_back();
	return av;
}

long long count_tastiness(long long xx, std::vector<long long> aa) {
	x = xx;
	memset(a, 0, sizeof a);
	memset(sum, 0, sizeof sum);
	for(int i = 0; i < int(aa.size()); i++){
		a[i] = aa[i];
		sum[i] = a[i] * (1ll << i);
		if(i)
			sum[i] += sum[i - 1];
	}
	for(int i = aa.size(); i < 60; i++)
		sum[i] = sum[i - 1];
	vector <ll> av;
	av = solve(59, av);
	//cout << "hey " << av.size() << endl;
	return av.back();
}

Compilation message (stderr)

biscuits.cpp: In function 'std::vector<long long int> solve(int, std::vector<long long int>)':
biscuits.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int j = 0; j < need.size(); j++)
      |                 ~~^~~~~~~~~~~~~

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