Submission #1183195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183195		PieArmy	Group Photo (JOI21_ho_t3)	C++20	100 / 100	383 ms	197160 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

const ll inf=1000000000;

struct Fen{
	int n;
	int sum=0;
	vector<int>tree;
	void init(int N){
		n=N;
		sum=0;
		tree.resize(n+1,0);
	}
	void update(int tar,int x){
		sum+=x;
		while(tar<=n){
			tree[tar]+=x;
			tar+=(tar&-tar);
		}
	}
	int query(int tar){
		int res=0;
		while(tar){
			res+=tree[tar];
			tar-=(tar&-tar);
		}
		return res;
	}
};

int n;
int arr[5023],loc[5023];
ll dp[5023][5023];
Fen fen;
int pref[5023];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	fen.init(n);
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		loc[arr[i]]=i;
	}
	for(int i=1;i<=n+1;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=inf;
		}
	}
	dp[1][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			pref[j]=pref[j-1]+(arr[j]>i);
		}
		ll cos=0;
		for(int j=i-1;j>=0;j--){
			cos+=fen.sum-fen.query(loc[j+1]);
			fen.update(loc[j+1],1);
			cos+=pref[loc[j+1]];
			dp[i+1][i]=min(dp[i+1][i],dp[i][j]+cos);
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
		fen.tree.clear();
		fen.init(n);
	}
	cout<<dp[n+1][n];
}

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