Submission #574323

#	Time	Username	Problem	Language	Result	Execution time	Memory
574323		benson1029	Group Photo (JOI21_ho_t3)	C++14	100 / 100	356 ms	67540 KiB

Main

#include<bits/stdc++.h>
using namespace std;

int n;
int a[5005];
int par[5005][5005];
int dp[5005];

int main() {
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];
	
	int ans = 0;
	for(int i=1; i<=n; i++) {
		for(int j=i+1; j<=n; j++) {
			if(a[i] > a[j]) {
				par[a[j]][a[i]]++;
				ans++;
			}
		}
	}
	
	for(int l=0; l<n; l++) {
		for(int i=1; i<=n-l; i++) {
			int j = i+l;
			par[i][j] += par[i+1][j] + par[i][j-1] - par[i+1][j-1];
		}
	}
	
	for(int i=1; i<=n; i++) {
		dp[i] = -1e9;
		for(int j=0; j<i; j++) {
			dp[i] = max(dp[i], dp[j] + 2*par[j+1][i] - (i-j)*(i-j-1)/2);
		}
	}
	
	cout << ans-dp[n] << "\n";
}

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