Submission #814809

#	Time	Username	Problem	Language	Result	Execution time	Memory
814809		rainboy	Garden (JOI23_garden)	C11	100 / 100	1604 ms	122660 KiB

garden

#include <stdio.h>

#define N	5000

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static char uu[N], vv[N], ww[N][N];
	static int aa[N], aaa[N][N], qu[N], pp[N], qq[N];
	int n, m1, m2, cnt, i, i_, j, a, ans;

	scanf("%d%d%d", &m1, &m2, &n);
	while (m1--) {
		scanf("%d%d", &i, &j);
		uu[i] = 1, vv[j] = 1;
	}
	while (m2--) {
		scanf("%d%d", &i, &j);
		ww[i][j] = 1;
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (ww[i][j]) {
				i_ = i, a = n;
				do
					aaa[i_ = (i_ + 1) % n][j] = a--;
				while (!ww[i_][j]);
			}
	a = n - 1;
	while (!uu[a])
		a--;
	a++;
	ans = n * n;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			aa[j] = vv[j] ? n + 1 : max(aaa[i][j], a);
		cnt = 0;
		for (j = 0; j < n; j++) {
			while (cnt && aa[qu[cnt - 1]] <= aa[j])
				cnt--;
			qu[cnt++] = j;
		}
		for (j = 0; j < n; j++) {
			while (cnt && aa[qu[cnt - 1]] <= aa[j])
				cnt--;
			if (cnt == 0)
				pp[j] = -1;
			else {
				pp[j] = qu[cnt - 1];
				if (pp[j] > j)
					pp[j] -= n;
			}
			qu[cnt++] = j;
		}
		cnt = 0;
		for (j = n - 1; j >= 0; j--) {
			while (cnt && aa[qu[cnt - 1]] <= aa[j])
				cnt--;
			qu[cnt++] = j;
		}
		for (j = n - 1; j >= 0; j--) {
			while (cnt && aa[qu[cnt - 1]] <= aa[j])
				cnt--;
			if (cnt == 0)
				qq[j] = -1;
			else {
				qq[j] = qu[cnt - 1];
				if (qq[j] < j)
					qq[j] += n;
			}
			qu[cnt++] = j;
		}
		ans = min(ans, a * n);
		for (j = 0; j < n; j++)
			if (aa[j] != n + 1)
				ans = min(ans, aa[j] * (n - (qq[j] - pp[j] - 1)));
		a = uu[i] ? n : a - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

garden.c: In function 'main':
garden.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d%d", &m1, &m2, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%d", &i, &j);
      |   ^~~~~~~~~~~~~~~~~~~~~
garden.c:19:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d%d", &i, &j);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25