Submission #441842

#	Time	Username	Problem	Language	Result	Execution time	Memory
441842		FSYo	Packing Biscuits (IOI20_biscuits)	C++14	9 / 100	14 ms	784 KiB

biscuits

#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
typedef long long ll;
cs int N = 64; 
ll sm[N], dp[N][N], lm[N];

ll count_tastiness(ll x, vector<ll> a) {
	a.resize(61);
	memset(sm, 0, sizeof sm);
	for(int i = 0; i < 61; i++)
		sm[i] = (i ? sm[i - 1] : 0) + (a[i] << i);
	for(int i = 0; i < 61; i++) {
		ll t = sm[i] / (1ll << i);
		lm[i] = sm[i] / x - (1ll << i);
		ll mask = (1ll << i) - 1; 
		lm[i] = min(lm[i], mask);
	}
	memset(dp, 0, sizeof dp);
	dp[61][61] = 1; 
	for(ll i = 60, c; ~i; i--) {
		// first 
		dp[i][61] = dp[i + 1][61];
		if(lm[i] >= 0) dp[i][i] = dp[i + 1][61]; 
		ll mask = (1ll << i) - 1;
		for(int j = i + 1; j <= 60; j++) 
		if(c = dp[i + 1][j]){
			// choose 
			if(lm[j] >> i & 1) {
				if((lm[j] & mask) > lm[i]) 
					dp[i][i] += c; 
				else 	
					dp[i][j] += c; 
			}
			// not choose
			if(lm[j] >> i & 1) {
				dp[i][61] += c; 
			}
			else {
				dp[i][j] += c; 
			}
		}
	}
	ll ans = 0; 
	for(int i = 0; i <= 61; i++)
		if(lm[i] >= 0) ans += dp[0][i];
	return ans; 
}

#ifdef FSYo
int main() {
	freopen("1.in", "r", stdin);
	int T;
	cin >> T; 
	while(T--) {
		ll k, x; 
		cin >> k >> x; 
		vector<ll> a(k);
		for(int i = 0; i < k; i++)
			cin >> a[i];
		cout << count_tastiness(x, a) << '\n';
	}
	return 0; 
}
#endif

Compilation message (stderr)

biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:15:6: warning: unused variable 't' [-Wunused-variable]
   15 |   ll t = sm[i] / (1ll << i);
      |      ^
biscuits.cpp:28:8: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   28 |   if(c = dp[i + 1][j]){
      |      ~~^~~~~~~~~~~~~~

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