Submission #708025

#	Time	Username	Problem	Language	Result	Execution time	Memory
708025		rainboy	Group Photo (JOI21_ho_t3)	C11	100 / 100	199 ms	67408 KiB

Main

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

#define N	5000

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

int main() {
	static int aa[N], cc[N + 1][N + 1], dp[N + 1];
	int n, i, j, a, b, cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	cnt = 0;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (aa[i] < aa[j])
				cc[aa[i]][aa[j] + 1]++;
			else
				cc[aa[j]][aa[i] + 1]--, cnt++;
	for (a = n; a >= 0; a--)
		for (b = a + 1; b <= n; b++)
			cc[a][b] += cc[a + 1][b];
	for (a = n; a >= 0; a--)
		for (b = a + 1; b <= n; b++)
			cc[a][b] += cc[a][b - 1];
	memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = cnt;
	for (a = 0; a < n; a++)
		for (b = a + 1; b <= n; b++)
			dp[b] = min(dp[b], dp[a] + cc[a][b]);
	printf("%d\n", dp[n]);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
Main.c:14:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d", &aa[i]), aa[i]--;
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36