제출 #833819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
833819		penguinman	Packing Biscuits (IOI20_biscuits)	C++17	0 / 100	3 ms	340 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using ll = long long;
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(), a.end()

constexpr ll inf = (1ll<<60);

ll subtask_1_2_3(ll x, vi a){
	ll k = a.size();
	while(k <= 60){
		a.pb(0);
		k++;
	}
	//assert(x <= 10000);
	vi remain(1,0), val(1,1);
	rep(i,0,k){
		vector<pii> data;
		rep(j,0,remain.size()){
			data.pb(mp((remain[j]+a[i])/2, val[j]));
			if(remain[j]+a[i] >= x){
				data.pb(mp((remain[j]+a[i]-x)/2, val[j]));
			}
		}
		sort(all(data));
		remain.clear();
		val.clear();
		remain.pb(data[0].first);
		val.pb(0);
		for(auto el: data){
			if(el.first == remain.back()) val[val.size()-1] += el.second;
			else{
				remain.pb(el.first);
				val.pb(el.second);
			}
		}
	}
	ll ans = 0;
	for(auto el: val) ans += el;
	return ans;
}



long long count_tastiness(long long x, std::vector<long long> a) {
	//if(x <= 10000) return subtask_1_2_3(x,a);
	ll k = a.size();
	while(k <= 60){
		a.pb(0);
		k++;
	}
	vi sum(k);
	rep(i,0,k){
		if(i) sum[i] = sum[i-1];
		sum[i] += (1ll<<i)*a[i];
	}
	vi dp(k);
	vi require(k);
	rep(i,0,k){
		if(sum[i]/(1ll<<i) < x){
			require[i] = -1;
			continue;
		}
		else{
			require[i] = (sum[i]-(1ll<<i)*x)/x;
		}
	}
	per(i,k-1,0){
		if(require[i] == -1) continue;
		dp[i]++;
		if(require[i] >= (1ll<<i)){
			rep(j,0,i){
				if(require[j] != -1) dp[j] += dp[i];
			}
			continue;
		}
		ll cnt = 0;
		per(j,i-1,0){
			if(require[j] != -1){
				dp[j] += cnt*dp[i];
			}
			if(require[i] & (1ll<<j)){
				if(require[j] == -1){
					cnt++;
					rep(k,0,j){
						if(require[k] != -1){
							dp[k] += cnt*dp[i];
						}
					}
					break;
				}
				require[i] -= (1ll<<j);
				if(require[i] >= require[j]){
					cnt++;
					dp[j] += dp[i];
					rep(k,0,j){
						if(require[k] != -1){
							dp[k] += cnt*dp[i];
						}
					}
					break;
				}
				cnt++;
			}
		}
	}
	ll ans = 1;
	rep(i,0,k){
		if(require[i] == -1) continue;
		ans += dp[i];
	}
	return ans;
}

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