Submission #814206

#	Time	Username	Problem	Language	Result	Execution time	Memory
814206		MohamedAhmed04	Group Photo (JOI21_ho_t3)	C++14	100 / 100	207 ms	67672 KiB

Main

#include <bits/stdc++.h>

using namespace std ;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds ;

template<class T> using ordered_set = tree<T , null_type , less<T> , rb_tree_tag , tree_order_statistics_node_update> ;

const int MAX = 5000 + 10 ;

int arr[MAX] ;
int n ;

int pos[MAX] , cnt[MAX] , cnt2[MAX][MAX] ;
int dp[MAX] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	ordered_set<int>s ;
	for(int i = 1 ; i <= n ; ++i)
	{
		pos[arr[i]] = i ;
		cnt[i] = s.size() - s.order_of_key(arr[i]) ;
		s.insert(arr[i]) ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = i-1 ; j >= 1 ; --j)
			cnt2[i][j] = cnt2[i][j+1] + (pos[j] < pos[i]) ;
	}
	for(int i = n ; i >= 1 ; --i)
	{
		dp[i] = 1e9 ;
		int inv = 0 ;
		for(int j = i ; j <= n ; ++j)
		{
			inv += cnt[j] ;
			inv += cnt2[j][i] ;
			inv -= (j-i) - cnt2[j][i] ;
			dp[i] = min(dp[i] , dp[j+1] + inv) ;
		}
	}
	return cout<<dp[1]<<"\n" , 0 ;
}		

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