Submission #961131

#	Time	Username	Problem	Language	Result	Execution time	Memory
961131		happy_node	Group Photo (JOI21_ho_t3)	C++17	100 / 100	936 ms	196732 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], sum[MX][MX], diag[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++) {
		for(int j=H[i];j<=N;j++) curCnt[j]++;
		for(int j=1;j<=N;j++) cnt[H[i]][j]=curCnt[j];
	}

	for(int j=1;j<=N;j++) {
		for(int i=1;i<=N;i++) {
			sum[i][j]+=sum[i-1][j];
			sum[i][j]+=cnt[i][j];
		}
	}

	for(int j=1;j<=N;j++) {
		diag[j]+=diag[j-1];
		diag[j]+=cnt[j][j-1];
	}

	for(int i=0;i<=N;i++) {
		for(int k=i+1;k<=N;k++) {
			int cost=0;
			cost+=sum[k][N]-sum[i][N];
			cost-=sum[k][k]-sum[i][k];
			cost-=sum[k][i]-sum[i][i];
			cost+=diag[k]-diag[i];
			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: 36 / 36