Submission #771218

#	Time	Username	Problem	Language	Result	Execution time	Memory
771218		Trisanu_Das	Group Photo (JOI21_ho_t3)	C++17	100 / 100	230 ms	67464 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
int a[5005], pos[5005], dp[5005], ulta[5005][5005];
 
signed main(){
	int n; cin >> n;
	for(int i = 1; i < n + 1; i++){
		cin >> a[i];
		pos[a[i]] = i;
	}
	for(int i = 2; i < n + 1; i++){
		int cnt = 0;
		for(int j = i - 1; j > 0; j--){
			if(pos[j] > pos[i]) cnt++;
			ulta[j][i] = ulta[j][i - 1] + cnt;
		}
	}
	for(int i = 1; i < n + 1; i++){
		dp[i] = INT_MAX;
		for(int j = 0; j < i; j++){
			dp[i] = min(dp[i], dp[j] + ulta[1][i] - ulta[1][j] + ((i - j) * (i - j - 1)) / 2 - 2 * ulta[j + 1][i]);
		}
	}
	cout << dp[n] << '\n';
}

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