Submission #528161

#	Time	Username	Problem	Language	Result	Execution time	Memory
528161		Jasiekstrz	Group Photo (JOI21_ho_t3)	C++17	100 / 100	212 ms	134468 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=5e3;
int g[N+10];
int f[N+10][N+10];
int c[N+10][N+10];
int dp[N+10];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		g[x]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=n-1;j>=i;j--)
			f[i][j]=f[i][j+1]+(g[j+1]<g[i]);
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=i;j<=n;j++)
			c[i][j]=c[i+1][j]+j-i+2*f[i][j]-f[i][i];
	}
	//cerr<<f[1][1]<<"\n";
	for(int i=1;i<=n;i++)
	{
		dp[i]=1e9+7;
		for(int j=1;j<=i;j++)
			dp[i]=min(dp[i],dp[j-1]+c[j][i]);
		//cerr<<i<<": "<<dp[i]<<"\n";
	}
	cout<<dp[n]<<"\n";
	return 0;
}

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