Submission #961105

#	Time	Username	Problem	Language	Result	Execution time	Memory
961105		happy_node	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5015 ms	468 KiB

Main

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

const int MX=5005;

int N;
int H[MX], dp[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=0;i<=N;i++) {
		for(int k=i+1;k<=N;k++) {
			int cost=0;
			for(int j=k;j>i;j--) {
				for(int x=1;x<=N;x++) {
					if(H[x]==j) break;
					cost+=(i<H[x]&&H[x]<j)||k<H[x];
				}
			}
			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: 0 / 20
• Subtask 5: 0 / 36