Submission #1312047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312047		Faisal_Saqib	Group Photo (JOI21_ho_t3)	C++20	44 / 100	5092 ms	2880 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};
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			left[i][j]=1;
		}
	}
	for(int i=0;i<=n;i++)dp[i]=1e9;
		dp[0]=0;
	for(int i=0;i<=n;i++)
	{
		// length of suffix fixed
		// cout<<"For "<<i<<' '<<dp[i]<<endl;
		for(int p=1;p<=n-i;p++)
		{
			int fe=n-i,le=p;
			int sm=dp[i];
			// for(int k=p;k<=n-i;k++)
			for(int k=n-i;k>=p;k--)
			{
				// we place element fs at position k
				// so we want suffix sum left[i][pos[fs]]
				for(int ci=pos[le];ci<=n;ci++)
				{
					if(p<=a[ci] and a[ci]<=le)
					{
						// cost is set to zero
					}
					else
						sm+=left[i][ci];
				}
				le++;
			}
			// p is the pos
			// number fixed n-p+1
			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: 0 / 20
• Subtask 5: 0 / 36