Submission #592772

#	Time	Username	Problem	Language	Result	Execution time	Memory
592772		rainboy	Boarding Passes (BOI22_passes)	C11	100 / 100	102 ms	23420 KiB

passes

#include <stdio.h>
#include <string.h>

#define N	100000
#define A	15

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

int main() {
	static char cc[N + 1];
	static int ii[A][N], kk[N], ll[A][N];
	static long long dp[A][A][N + 1], dq[A][1 << A], dr[1 << A];
	int n, h, i, a, a_, b, lower, upper;
	long long x;

	scanf("%s", cc), n = strlen(cc);
	for (i = 0; i < n; i++) {
		a = cc[i] - 'A';
		for (a_ = 0; a_ < A; a_++)
			ll[a_][i] = kk[a_];
		ii[a][kk[a]++] = i;
	}
	for (a = 0; a < A; a++)
		for (a_ = 0; a_ < A; a_++) {
			for (h = 0; h < kk[a]; h++) {
				i = ii[a][h];
				dp[a][a_][0] += kk[a_] - ll[a_][i];
			}
			for (h = 0; h < kk[a]; h++) {
				i = ii[a][h];
				dp[a][a_][h + 1] = dp[a][a_][h] + ll[a_][i] * 2 - kk[a_];
			}
		}
	for (b = 0; b < 1 << A; b++)
		for (a = 0; a < A; a++)
			if ((b & 1 << a) == 0) {
				lower = -1, upper = kk[a];
				while (upper - lower > 1) {
					h = (lower + upper) / 2;
					i = ii[a][h];
					x = h - (kk[a] - 1 - h);
					for (a_ = 0; a_ < A; a_++)
						if ((b & 1 << a_) != 0)
							x += (dp[a][a_][h + 1] - dp[a][a_][h]) * 2;
					if (x > 0)
						upper = h;
					else
						lower = h;
				}
				h = upper;
				dq[a][b] = (long long) h * (h - 1) / 2 + (long long) (kk[a] - h) * (kk[a] - h - 1) / 2;
				for (a_ = 0; a_ < A; a_++)
					if ((b & 1 << a_) != 0)
						dq[a][b] += dp[a][a_][h] * 2;
			}
	memset(dr, 0x3f, (1 << A) * sizeof *dr);
	dr[0] = 0;
	for (b = 0; b < 1 << A; b++)
		for (a = 0; a < A; a++)
			if ((b & 1 << a) == 0)
				dr[b | 1 << a] = min(dr[b | 1 << a], dr[b] + dq[a][b]);
	if (dr[(1 << A) - 1] % 2 == 0)
		printf("%lld\n", dr[(1 << A) - 1] / 2);
	else
		printf("%lld.%lld\n", dr[(1 << A) - 1] / 2, dr[(1 << A) - 1] % 2 * 5);
	return 0;
}

Compilation message (stderr)

passes.c: In function 'main':
passes.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%s", cc), n = strlen(cc);
      |  ^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 25 / 25
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40