제출 #1187018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187018		hengliao	비스킷 담기 (IOI20_biscuits)	C++20	0 / 100	1093 ms	840 KiB

biscuits

#pragma GCC optimize("O4,Ofast")
#include "biscuits.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define vll vector<ll>
#define pll pair<ll, ll>
#define pb push_back

typedef long long ll;
typedef __int128 i128;

namespace{
	ll x, k;
	const ll mxN=63;
	const ll inf=2e18;
	ll a[mxN];
	ll pw[mxN];
	vector<pll> v[mxN];
	ll ans;
	ll pre[mxN];
}

void f(ll pos, ll add){
	ll tep=a[pos]+add;
	ans++;
	tep-=x;
	tep*=pw[pos];
	for(auto &[x, y]:v[pos]){
		if(tep<x){
			break;
		}
		ll tep2=tep;
		tep2+=pre[y]-pre[pos];
		tep2/=pw[y];
		f(y, tep2);
	}
	ll tep2=pre[k-1]-pre[pos]+tep;
	tep2/=pw[k];
	ans+=tep2/x;
}

long long count_tastiness(long long X, vector<long long> A) {
	k=A.size();
	for(ll i=0;i<k;i++){
		v[i].clear();
	}
	x=X;
	pw[0]=1;
	for(ll i=0;i<k;i++){
		a[i]=A[i];
	}
	for(ll i=1;i<=k;i++){
		pw[i]=pw[i-1]*2;
	}
	for(ll i=0;i<k;i++){
		ll sum=0;
		for(ll j=i+1;j<k;j++){
			sum+=pw[j]*a[j];
			i128 need=(i128) pw[j]*x-sum;
			need=min(need, (i128) inf);
			v[i].pb({(ll) need, j});
		}
		sort(v[i].begin(), v[i].end());
	}
	pre[0]=pw[0]*a[0];
	for(ll i=1;i<k;i++){
		pre[i]=pre[i-1]+pw[i]*a[i];
	}
	ans=1;
	for(ll i=0;i<k;i++){
		ll add=0;
		if(i>0){
			add+=pre[i-1];
		}
		add/=pw[i];
		if(a[i]+add>=x){
			f(i, add);
		}
	}
	if(pre[k-1]/pw[k]>=x){
		ans+=pre[k-1]/pw[k]/x;
	}
	// cout<<-1<<' ';
	// for(ll i=0;i<k;i++){
	// 	vll new_add;
	// 	for(auto &it:add){
	// 		ll tep=it+a[i];
	// 		new_add.pb(tep/2);
	// 		if(tep>=x){
	// 			ans++;
	// 			// cout<<i<<' ';
	// 			tep-=x;
	// 			new_add.pb(tep/2);
	// 		}
	// 	}
	// 	add=new_add;
	// }
	// // cout<<'\n';
	// for(auto &it:add){
	// 	ans+=it/x;
	// 	// cout<<it<<' ';
	// }
	// cout<<'\n';
	return ans;
}

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