Submission #1312425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312425		neonglitch	Group Photo (JOI21_ho_t3)	C++20	100 / 100	3908 ms	294252 KiB

Main

#include <iostream>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a[n+1],pos[n+1]={0};
	for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
	int dp[n+1]={0};
	int left[n+1][n+1]={0};
	int cst[n+1][n+1]={0};
	int pre[n+2]={0};
	int ppre[n+2]={0};
	int cpr[n+1][n+1]={0};
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			left[i][j]=1;
			cst[i][j]=0;
		}
	}
	for(int i=0;i<=n;i++)dp[i]=1e9;
		dp[0]=0;
	for(int l=1;l<=n;l++)
	{
		for(int r=1;r<=n;r++)
		{
			cpr[r][l]=cpr[r-1][l]+(pos[l]<=pos[r]);
		}
	}
	
	for(int l=1;l<=n;l++)
	{
		cst[l][l]=1;
		for(int r=l+1;r<=n;r++)
		{
			cst[l][r]=cst[l][r-1] +cpr[r][r]-cpr[l-1][r];
		}
	}
	for(int i=0;i<=n;i++)
	{
		// length of suffix fixed
		// cout<<"For "<<i<<' '<<dp[i]<<endl;
		for(int j=0;j<=n;j++)pre[j]=left[i][j];
		for(int j=n-1;j>=0;j--)pre[j]+=pre[j+1];
		for(int j=0;j<=n;j++)ppre[j]=pre[pos[j]];
		for(int j=1;j<=n;j++)ppre[j]+=ppre[j-1];
		for(int p=1;p<=n-i;p++)
		{
			int fe=n-i,le=p;
			int sm=dp[i];

			sm+=ppre[fe]-ppre[le-1]-cst[le][fe];

			if(sm<dp[n-p+1])
			{
				dp[n-p+1]=sm;
				for(int j=0;j<=n;j++)
				{
					if(p<=a[j] and a[j]<=n-i)
					{
						left[n-p+1][j]=0;
					}
					else{
						left[n-p+1][j]=left[i][j];
					}
				}
			}
		}
	}
	cout<<dp[n]<<endl;
}

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