Submission #370945

#	Time	Username	Problem	Language	Result	Execution time	Memory
370945		kshitij_sodani	Group Photo (JOI21_ho_t3)	C++14	100 / 100	781 ms	313324 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n;
llo it[5001];
llo dp[5001];
llo ind[5001];
llo cost[5001][5001];
llo pre[5001][5001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		ind[it[i]]=i;
	}
	for(llo i=1;i<=n;i++){
		for(llo j=1;j<=n;j++){
			pre[i][j]=pre[i][j-1];
			if(ind[j]>ind[i]){
				pre[i][j]++;
			}
		}
	}
	/*for(int i=1;i<=3;i++){
		cout<<pre[3][i]<<",,";
	}
	cout<<endl;*/
	for(llo i=1;i<=n;i++){
		for(llo j=i;j<=n;j++){
			cost[i][j]=0;
			if(i<j){
				cost[i][j]+=cost[i][j-1];
			}
			cost[i][j]+=pre[j][i-1];
			if(i<j){
				cost[i][j]+=(j-i)-(pre[j][j-1]-pre[j][i-1]);
			}
		}
	}
	/*cout<<cost[1][1]<<":"<<cost[1][2]<<":"<<cost[2][3]<<endl;
	cout<<cost[1][3]<<":"<<cost[4][5]<<endl;*/
	for(llo i=0;i<=n;i++){
		dp[i]=1e9;
	}
	dp[0]=0;
	for(llo i=1;i<=n;i++){
		for(llo j=1;j<=i;j++){
			dp[i]=min(dp[i],dp[j-1]+cost[j][i]);
		}
		/*for(llo j=0;j<n;j++){
			for(llo k=0;k<n;k++){

			}
		}*/
	}

	cout<<dp[n]<<endl;





 
	return 0;
}

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