Submission #386866

#	Time	Username	Problem	Language	Result	Execution time	Memory
386866		nikatamliani	Group Photo (JOI21_ho_t3)	C++14	100 / 100	760 ms	313800 KiB

Main

#include <iostream>
#define ll long long
using namespace std;
const int N = 5e3+5;
ll n, a[N], id[N], dp[N], cnt[N][N], cost[N][N];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		id[a[i]] = i;
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = n; j >= 1; --j) {
			cnt[i][j] = cnt[i][j+1] + (id[j] < id[i]);
		}
	}
	for(int L = 1; L <= n; ++L) {
		for(int R = L; R <= n; ++R) {
			cost[L][R] = cost[L][R - 1] + cnt[R][L] - (R - L - (cnt[R][L] - cnt[R][R+1]));
		}
	}
	for(int i = 1; i <= n; ++i) {
		dp[i] = 1e15;
		for(int j = 0; j < i; ++j) {
			dp[i] = min(dp[i], dp[j] + cost[j+1][i]);
		}
	}
	cout << dp[n] << endl;
}

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