Submission #1282297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282297		kaiboy	Group Photo (JOI21_ho_t3)	C++20	100 / 100	224 ms	165248 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 5000;

int aa[N], ii[N], kk[N][N], xx[N][N], dp[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i], ii[--aa[i]] = i;
	for (int a = 0; a < n; a++) {
		if (a)
			for (int i = 0; i < n; i++)
				kk[a][i] = kk[a - 1][i];
		for (int i = ii[a]; i < n; i++)
			kk[a][i]++;
	}
	for (int l = 0; l < n; l++)
		for (int k = 0, r = l; r < n; r++) {
			k += l;
			if (r)
				k += kk[r - 1][ii[r]];
			if (l)
				k -= kk[l - 1][ii[r]] * 2;
			xx[l][r] = k;
		}
	for (int i = 0; i < n; i++) {
		dp[i] = xx[0][i];
		for (int j = 0; j < i; j++)
			dp[i] = min(dp[i], dp[j] + xx[j + 1][i]);
	}
	cout << dp[n - 1] << '\n';
	return 0;
}

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