Submission #457991

#	Time	Username	Problem	Language	Result	Execution time	Memory
457991		rainboy	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	21 ms	1356 KiB

biscuits

#include "biscuits.h"

using namespace std;

typedef vector<long long> vll;

const int N = 60;

long long min(long long a, long long b) { return a < b ? a : b; }

long long lim[N], dp[N][N];

long long count_tastiness(long long x, vll aa) {
	int n = aa.size(), i, j;
	long long a;

	a = 0;
	for (i = 0; i < N; i++) {
		if (i < n)
			a += aa[i] << i;
		lim[i] = min(a / x, (1LL << i + 1) - 1);
	}
	for (i = 0; i < N; i++)
		for (j = i; j < N; j++) {
			if (i == 0)
				dp[i][j] = (lim[j] & 1LL << i) != 0 ? 2 : 1;
			else
				dp[i][j] = ((lim[j] & 1LL << i) != 0 ? dp[i - 1][i - 1] : 0) + dp[i - 1][(lim[j] & (1LL << i) - 1) < (lim[i - 1] & (1LL << i) - 1) ? j : i - 1];
		}
	return dp[N - 1][N - 1];
}

Compilation message (stderr)

biscuits.cpp: In function 'long long int count_tastiness(long long int, vll)':
biscuits.cpp:21:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   21 |   lim[i] = min(a / x, (1LL << i + 1) - 1);
      |                               ~~^~~
biscuits.cpp:28:99: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |     dp[i][j] = ((lim[j] & 1LL << i) != 0 ? dp[i - 1][i - 1] : 0) + dp[i - 1][(lim[j] & (1LL << i) - 1) < (lim[i - 1] & (1LL << i) - 1) ? j : i - 1];
      |                                                                                        ~~~~~~~~~~~^~~
biscuits.cpp:28:131: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |     dp[i][j] = ((lim[j] & 1LL << i) != 0 ? dp[i - 1][i - 1] : 0) + dp[i - 1][(lim[j] & (1LL << i) - 1) < (lim[i - 1] & (1LL << i) - 1) ? j : i - 1];
      |                                                                                                                        ~~~~~~~~~~~^~~

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