Submission #703226

#	Time	Username	Problem	Language	Result	Execution time	Memory
703226		ld_minh4354	Group Photo (JOI21_ho_t3)	C++17	100 / 100	3527 ms	1180 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;
		while (s.begin()!=s.end()) s.erase(s.begin());
		
		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;
		
		cost=0;
		for (j=i;j<n+1;j++)
		{
			cost += pos[j] - 1 - s.order_of_key(-pos[j]);
			s.insert(-pos[j]);
			
			dp[i]=min(dp[i], cost + dp[j+1]);
			
//			cout<<i<<" "<<j<<" :"<< cost+dp[j+1]<<"\n";
		}
	}
	
	cout<<dp[1];
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:25:12: warning: unused variable 'k' [-Wunused-variable]
   25 |  int n,i,j,k,a[5005],dp[5005],b[5005],m,cost,pos[5005];
      |            ^

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