Submission #378387

#	Time	Username	Problem	Language	Result	Execution time	Memory
378387		astoria	Group Photo (JOI21_ho_t3)	C++14	100 / 100	431 ms	98568 KiB

Main

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

int mn(int i, int j){
	if(i!=-1&&j!=-1) return min(i,j);
	else return max(i,j);
}

int main() {
	int n; cin>>n;
	int h[n+5];
	for(int i=0; i<n; i++){ cin>>h[i]; h[i]=h[i]-1;}
	int ord[n+5];
	for(int i=0; i<n; i++) ord[h[i]] = i;

	int supp[n+5][n+5];  //cntup[pos][num] = count #(position > pos && number >= num)
	memset(supp,0,sizeof(supp));
	for(int j=n-1; j>=1; j--) {
		for(int i=0; i<=h[j]; i++) supp[j-1][i]=supp[j][i]+1;
		for(int i=h[j]+1; i<=n; i++) supp[j-1][i]=supp[j][i];
	}

	int dp[n+5]; memset(dp,-1,sizeof(dp));
	dp[0] = 0;
	for(int i=1; i<=n; i++) {
		int trans=0;
		for(int j=i-1; j>=0; j--){
			trans += (supp[ord[j]][j]-(2*supp[ord[j]][i])+(n-i));
			dp[i]=mn(dp[i],dp[j]+trans);
		}
	}
	cout<<dp[n];
}

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