제출 #813800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
813800		joonwu04	비스킷 담기 (IOI20_biscuits)	C++17	100 / 100	21 ms	1236 KiB

biscuits

#include "biscuits.h"
#include <vector>

using namespace std;

typedef long long ll;

ll b[61], c[70], var[70]; //cIdx는 1부터 사용 c[0]=0 
int aSize, cSize;
ll dp[70]; // dp[i]: c[1]~c[i] 만 사용해서 만들 수 있는 y의 개수 

void makeDp(ll x, int i);
ll useI(ll x, int i);
int changeVar(ll x, int i);
void setup(ll x, vector<ll> a);

long long count_tastiness(long long x, std::vector<long long> a) {
	setup(x, a);
	for(int i=0; i<=60; i++) {
		for(int i=0; i<70; i++) {
			var[i] = c[i];
		}
		
		makeDp(x, i);
	}
	return dp[60];
	/*return sub2(x);
	return sub1(x, 0);*/
}

void makeDp(ll x, int i) { // c[1]~c[i]만 사용해서 만들 수 있는 y의 개수 
	if(i == 0) {
		dp[i] = 1;
	}
	else if(c[i] >= x) {
		dp[i] = 2*dp[i-1];
	}
	else {
		dp[i] = dp[i-1];
		dp[i] += useI(x, i);
	}
}

// var[i]<x
// to make var[i]=x, change var[1]~var[i-1] 
// in changed var[1]~var[i-1], count the number of possible y
ll useI(ll x, int i) {
	int nextI = changeVar(x, i);
	if(nextI == 0) return 0;
	
	ll t=dp[nextI-1];
	t += useI(x, nextI);
	return t;
}

// var[i]<x 
// to make var[i]=x, change var[1]~var[i-1]
// return finalIdx
int changeVar(ll x, int i) {
	ll t=0;
	for(int j=1; j<=i-1; j++) {
		t += var[j];
		t /= 2;
	}
	t += var[i];
	if(t < x) return 0;
	
	ll need = 2*(x-var[i]);
	for(int j=i-1; j>=1; j--) {
		if(var[j] >= need) {
			var[j] -= need;
			return j;
		}
		
		need -= var[j];
		var[j] = 0;
		need *= 2;
	}
	
	return 1;
}

void setup(ll x, vector<ll> a) {
	for(int i=0; i<70; i++) {
		c[i] = 0;
		dp[i] = 0;
	}
	
	for(int i=0; i<a.size(); i++) {
		c[i+1] = a[i];
	}
	cSize = a.size();
	
	for(int i=1; i<=cSize-1; i++) {
		if(c[i] > x+1) {
			ll move = (c[i]-x)%2==0 ? c[i]-x:c[i]-x-1;
			c[i+1] += move/2;
			c[i] -= move;
		}
	}
	for(int i=cSize; c[i] > x+1; i++) {
		ll move = (c[i]-x)%2==0 ? c[i]-x:c[i]-x-1;
		c[i+1] += move/2;
		c[i] -= move;
		cSize++;
	}
	
	for(int i=1; i<=cSize; i++) {
		var[i] = c[i];
	}
}

컴파일 시 표준 에러 (stderr) 메시지

biscuits.cpp: In function 'void setup(ll, std::vector<long long int>)':
biscuits.cpp:89:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i=0; i<a.size(); i++) {
      |               ~^~~~~~~~~

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