제출 #1153753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153753		KK_1729	Group Photo (JOI21_ho_t3)	C++17	100 / 100	334 ms	556 KiB

Main

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

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
	for (auto x: a) cout << x << " ";
	cout << endl;
}
struct Fenwick{
	vector<int> tree; int N;
	Fenwick(int n){
		tree.resize(n+1);
		this->N = n;
	}

	void add(int k, int x){
		while (k <= N){
			tree[k] += x;
			k += k&-k;
		}
	}

	int sum(int k){
		int ans = 0;
		while (k >= 1){
			ans += tree[k];
			k -= k&-k;
		}
		return ans;
	}
	int query(int l, int r){
		int ans = sum(r);
		if (l > 1) ans -= sum(l-1);
		return ans;
	}
};
void solve(){
	int n; cin >> n;
	vector<int> a(n+1);
	FOR(i,1,n+1) cin >> a[i];
	vector<int> ind(n+1);
	FOR(i,1,n+1) ind[a[i]] = i;
	vector<int> dp(n+1, 1e9);

	// printVector(ind);
	Fenwick o(n+1);
	vector<int> prefix(n+1);
	FOR(i,1,n+1){
		prefix[i] = o.query(ind[i], n+1);
		o.add(ind[i], 1);
	}
	dp[0] = 0;
	dp[1] = 0;
	for (int i = 2; i <= n; i++){
		Fenwick inv(n+1);
		int inversions = 0;
		int e = 0;
		for (int j = i-1; j >= 0; j--){
			e -= inv.sum(ind[j+1]);
			e += inv.query(ind[j+1], n+1);
			e += prefix[j+1];
			inv.add(ind[j+1], 1);
			dp[i] = min(dp[i], dp[j]+e);
		}
	}
	// printVector(dp);
	cout << dp[n] << endl;
}

int32_t main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);
	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: 36 / 36