Submission #715164

#	Time	Username	Problem	Language	Result	Execution time	Memory
715164		fruith	Group Photo (JOI21_ho_t3)	C++14	100 / 100	268 ms	67576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 5001, INF = 1e9;
 
int n, a[MAXN], p[MAXN], dp[MAXN], inv[MAXN][MAXN];
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
 
	cin >> n;
	for(int i=1; i<=n; ++i){
		cin >> a[i];
		p[a[i]] = i;
	}
 
	for(int j=2; j<=n; ++j){
		int c = 0;
		for(int i=j-1; i; --i){
			c += p[i] > p[j];
			inv[i][j] = inv[i][j-1] + c;
		}
	}
 
	for(int i=1; i<=n; ++i){
		dp[i] = INF;
		for(int j=0; j<i; ++j){
			dp[i] = min(dp[i], dp[j] + inv[1][i] - inv[1][j] + ((i-j)*(i-j-1))/2 - 2 * inv[j+1][i]);
		}
	}
	cout << dp[n];
}

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