제출 #716317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716317		rainboy	Monochrome Points (JOI20_monochrome)	C11	100 / 100	18 ms	7336 KiB

monochrome

#include <stdio.h>

#define N	200000

long long max(long long a, long long b) { return a > b ? a : b; }

long long aa[N + 1], bb[N + 1];

void update(int l, int r, int a, int b) {
	aa[l] += a, bb[l] += b, aa[r + 1] -= a, bb[r + 1] -= b;
}

int main() {
	static char cc[N * 2 + 1];
	static int iiw[N * 2], iib[N * 2];
	int n, nw, nb, i, iw, ib, iwl, iwr, ibl, ibr, l, r;
	long long ans;

	scanf("%d%s", &n, cc);
	iwl = iwr = ib = 0;
	iwl = iwr = ib = iwl;
	nw = nb = 0;
	for (i = 0; i < n * 2; i++)
		if (cc[i] == 'W')
			iiw[nw++] = i;
		else
			iib[nb++] = i;
	for (i = 0; i < n; i++) {
		iiw[n + i] = n * 2 + iiw[i];
		iib[n + i] = n * 2 + iib[i];
	}
	for (iw = 0, ibl = 0, ibr = 0; iw < n; iw++) {
		while (ibl < n * 2 && iib[ibl] < iiw[n + iw] - n)
			ibl++;
		while (ibr < n * 2 && iib[ibr] < iiw[n + iw])
			ibr++;
		if (ibl < ibr) {
			l = (ibl - iw + n * 2) % n, r = (ibr - 1 - iw + n * 2) % n;
			if (l <= r)
				update(l, r, -1, r);
			else
				update(0, r, -1, r), update(l, n - 1, -1, n + r);
		}
	}
	for (ib = 0, iwl = 0, iwr = 0; ib < n; ib++) {
		while (iwl < n * 2 && iiw[iwl] <= iib[n + ib] - n)
			iwl++;
		while (iwr < n * 2 && iiw[iwr] < iib[n + ib])
			iwr++;
		if (iwl < iwr) {
			l = (ib - iwr + 1 + n * 2) % n, r = (ib - iwl + n * 2) % n;
			if (l <= r)
				update(l, r, 1, -l);
			else
				update(l, n - 1, 1, -l), update(0, r, 1, n - l);
		}
	}
	for (i = 1; i < n; i++)
		aa[i] += aa[i - 1], bb[i] += bb[i - 1];
	ans = 0;
	for (i = 0; i < n; i++)
		ans = max(ans, aa[i] * i + bb[i]);
	printf("%lld\n", ans);
	return 0;
}

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

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

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65