Submission #891815

#	Time	Username	Problem	Language	Result	Execution time	Memory
891815		LCJLY	Group Photo (JOI21_ho_t3)	C++14	64 / 100	5058 ms	196904 KiB

Main

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

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

int prefix[5005][5005]; //pos val
int arr[5005];
int pos[5005];
int n=0;

int query(int l, int r, int val, int val2){
	if(val2<val) return 0;
	if(r<l) return 0; 
	int hold= prefix[r][val2]-prefix[r][val-1]-prefix[l-1][val2]+prefix[l-1][val-1];
	//show2(l,l,r,r);
	//show3(val,val,val2,val2,hold,hold);
	return hold;
}

int memo[5005];

int dp(int index){
	if(index==n+1) return 0;
	if(memo[index]!=-1) return memo[index];
	int ans=INT_MAX;
	
	for(int x=index;x<=n;x++){
		int cost=0;
		for(int y=index;y<=x;y++){
			//outside
			cost+=query(1,pos[y],x+1,n);
			//inside inversion
			cost+=query(1,pos[y],index,y-1);
			//show3(y,y,pos[y],pos[y],cost,cost);
		}
		int take=dp(x+1);
		//show3(index,index,x,x,cost,cost);
		//show(take,take);
		ans=min(ans,take+cost);
	}
	return memo[index]=ans;
}

void solve(){
	cin >> n;
	
	for(int x=1;x<=n;x++){
		cin >> arr[x];
		prefix[x][arr[x]]=1;
		pos[arr[x]]=x;
	}
	
	for(int x=1;x<=n;x++){
		for(int y=1;y<=n;y++){
			prefix[x][y]+=prefix[x-1][y]+prefix[x][y-1]-prefix[x-1][y-1];
		}
	}
	
	memset(memo,-1,sizeof(memo));
	cout << dp(1);
	
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("in.txt", "r", stdin);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}



		


		
		
	

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