oj.uz

Submission #385211

# Submission time Handle Problem Language Result Execution time Memory
385211 2021-04-03T16:46:10 Z rqi Packing Biscuits (IOI20_biscuits) C++14
0 / 100
 8 ms 364 KB 
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;

#define sz(x) (int)(x).size()
#define pb push_back

int k;
vl a;
ll x;

ll tpow[61];

bool possible(ll y){
	vl A = a;
	
	for(int i = 0; i <= 59; i++){
		if((y>>i)&1){
			A[i]-=x;
		}
		
		if(A[i] < 0) return 0;
		if(i+1 < 60){
			A[i+1]+=A[i]/2;
		}
	}
	//cout << y << "\n";
	return 1;
}

ll solveCase1(){
	while(sz(a) < 60){
		a.pb(0);
	}
	int ans = 0;
	for(int y = 0; y <= 100000; y++){
		if(possible(y)){
			ans++;
		}
	}
	return ans;
}

ll restr[60];
ll dp[60];

ll getDP(ll v, int bitnum){
	if(bitnum == 0){
		if(v == 0){
			return 1;
		}
		else if(v == 1){
			return dp[bitnum];
		}
		assert(false);
	}

	if(v < tpow[bitnum]){
		return getDP(v, bitnum-1);
	}

	if(restr[bitnum] < tpow[bitnum]){
		return getDP(v-tpow[bitnum], bitnum-1);
	}

	return dp[bitnum-1]+getDP(min(v-tpow[bitnum], restr[bitnum]-tpow[bitnum]), bitnum-1);
}

ll count_tastiness(ll _x, vl _a) {
	x = _x;
	a = _a;

	k = sz(a);

	tpow[0] = 1;
	for(int i = 1; i <= 60; i++){
		tpow[i] = tpow[i-1]*2;
	}

	// bool CASE1 = 1;

	// if(CASE1){
	// 	return solveCase1();
	// }

	restr[0] = a[0];
	for(int i = 1; i <= 59; i++){
		restr[i] = restr[i-1]+tpow[i]*a[i];
	}

	for(int i = 0; i <= 59; i++){
		restr[i]/=x;
	}

	if(restr[0] >= 1){
		dp[0] = 2;
	}
	else{
		dp[0] = 1;
	}

	for(int i = 1; i <= 59; i++){
		dp[i] = getDP(tpow[i+1]-1, i);
	}

	return dp[59];
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -