Submission #703218

#	Time	Username	Problem	Language	Result	Execution time	Memory
703218		ld_minh4354	Group Photo (JOI21_ho_t3)	C++17	44 / 100	5006 ms	596 KiB

Main

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

#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[5005];
	ordered_set s;
	
	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=1;j<m+1;j++) pos[b[j]]=j;
		
		for (j=i+1;j<=n+1;j++)
		{
			while (s.begin()!=s.end()) s.erase(s.begin());
			for (k=j;k<n+1;k++) s.insert(pos[k]);
			
			cost=0;
			for (k=i;k<j;k++)
			{
				cost += s.order_of_key(pos[k]);
				s.insert(pos[k]);
			}
			
//			cout<<i<<" "<<j<<" "<<cost<<"\n";
			
			dp[i]=min(dp[i], cost + dp[j]);
		}
	}
	
	cout<<dp[1];
}

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