Submission #397381

#	Time	Username	Problem	Language	Result	Execution time	Memory
397381		AQT	Group Photo (JOI21_ho_t3)	C++14	100 / 100	482 ms	452 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[5005];
int dp[5005];
int cst[5005][5005];
int bit[5005];
int pos[5005];

void upd(int p){
	p++;
	while(p <= N){
		bit[p]++;
		p += p&-p;
	}
}

int query(int p){
	p++;
	int ret = 0;
	while(p){
		ret += bit[p];
		p -= p & -p;
	}
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	/*
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	for(int i = 1; i <= N; i++){
		cin >> arr[i];
		if(i > 1 && arr[i] + 1 < arr[i-1]){
			pq.push(i-1);
		}
	}
	int ans = 0;
	while(pq.size()){
		int n =pq.top();
		pq.pop();
		if(arr[n+1] + 1 < arr[n]){
			swap(arr[n], arr[n+1]);
			if(n != 1 && arr[n] + 1 < arr[n-1]){
				pq.push(n-1);
			}
			if(n != N-1 && arr[n+2] + 1 < arr[n+1]){
				pq.push(n+1);
			}
			ans++;
		}
	}
	for(int i = 1; i <= N; i++){
		cout << arr[i] << " ";
	}
	cout << ans;
	*/
	/*
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> arr[i];
	}
	int ans = 0;
	int pos = 0;
	for(int l = 1; l <= N;){
		int r = l;
		for(int i = N; i; i--){
			if(arr[i] == r){
				r++;
			}
		}
		l = r;
		r--;
		for(int i = 1; i <= N; i++){
			if(arr[i] == r){
				pos++;
				for(int j = i-1; j >= pos; j--){
					ans++;
					swap(arr[j], arr[j+1]);
					for(int k = 1; k <= N; k++){
						cout << arr[k] << " ";
					}
					cout << "\n";
					cout << r << "\n";
				}
				r--;
			}
		}
	}
	cout << ans;
	*/
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> arr[i];
		pos[arr[i]] = i;
		dp[i] = INT_MAX/2;
	}
	for(int l = 1; l <= N; l++){
		fill(bit, bit+1+N, 0);
		int tot = 0;
		int idx = 0;
		for(int i = 1; i <= N; i++){
			if(arr[i] >= l){
				pos[arr[i]] = idx++;
			}
		}
		for(int r = l; r <= N; r++){
			tot += query(pos[r]);
			tot += pos[r];
			upd(pos[r]);
			dp[r] = min(dp[r], dp[l-1] + tot - (r - l) * (r - l + 1)/2);
		}
	}
	cout << dp[N];
}

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