Submission #961114

#	Time	Username	Problem	Language	Result	Execution time	Memory
961114		happy_node	Group Photo (JOI21_ho_t3)	C++17	64 / 100	5043 ms	98320 KiB

Main

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

const int MX=5005;

int N;
int H[MX], dp[MX], cnt[MX][MX], curCnt[MX], pos[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	for(int i=1;i<=N;i++) cin>>H[i];

	for(int i=1;i<=N;i++) dp[i]=1e9;

	for(int i=1;i<=N;i++) {
		pos[H[i]]=i;
		for(int j=H[i];j<=N;j++) curCnt[j]++;
		for(int j=1;j<=N;j++) cnt[i][j]=curCnt[j];
	}

	for(int i=0;i<=N;i++) {
		for(int k=i+1;k<=N;k++) {
			int cost=0;
			for(int j=k;j>i;j--) {
				int cur=0;
				cur+=cnt[pos[j]][N];
				cur-=cnt[pos[j]][k];
				cur+=cnt[pos[j]][j-1];
				cur-=cnt[pos[j]][i];

				cost+=cur;
			}
			dp[k]=min(dp[k],dp[i]+cost);
		}
	}

	cout<<dp[N]<<'\n';
}

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