Submission #703212

#	Time	Username	Problem	Language	Result	Execution time	Memory
703212		ld_minh4354	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5038 ms	436 KiB

Main

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"



signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int n,i,j,k,a[5005],dp[5005],b[5005],m,cost,pos;
	
	cin>>n;
	for (i=1;i<n+1;i++) cin>>a[i];
	
	dp[n]=dp[n+1]=0;
	for (i=n-1;i>0;i--)
	{
		dp[i]=1e12;
		
		m=0;
		for (j=1;j<n+1;j++) if (a[j]>=i)
		{
			m++;b[m]=a[j];
		}
		
		for (j=i+1;j<=n+1;j++)
		{
			cost=0;
			for (k=i;k<j;k++)
			{
				pos=1;
				while (b[pos]!=k)
				{
					if (b[pos]<k or b[pos]>=j) cost++;
//					cout<<pos<<" "<<cost<<" "<<k<<" "<<j<<" "<<b[pos]<<"\n";
					pos++;
				}
			}
			
			dp[i]=min(dp[i], cost + dp[j]);
//			cout<<i<<" "<<j<<" "<<cost+dp[j]<<"\n";
		}
	}
	
//	for (i=1;i<n+1;i++) cout<<dp[i]<<" ";
	
	cout<<dp[1];
}

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