제출 #1219340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219340		trimkus	Group Photo (JOI21_ho_t3)	C++20	64 / 100	717 ms	572 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 5000;
ll bit1[MAXN + 1], bit2[MAXN + 1];

void update(ll* bit, int i, int delta) {
	for (i += 1; i <= MAXN; i += i & -i) {
		bit[i] += delta;
	}
}

ll query(ll* bit, int r) {
	int res = 0;
	for (r += 1; r > 0; r-= r & -r) {
		res += bit[r];
	}
	return res;
}

ll query(ll* bit, int l, int r) {
	return query(bit, r) - query(bit, l - 1);
}


int main() {
	int n;
	cin >> n;
	vector<int> a(n + 1), pos(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pos[a[i]] = i;
	}
	vector<ll> dp(n + 1, LLONG_MAX);
	dp[0] = 0;
	for (int i = 1; i <= n; ++i) {
		ll inversions = 0;
		for (int j = 0; j <= MAXN; ++j) {
			bit1[j] = bit2[j] = 0;
		}
		for (int j = 1; j <= i; ++j) {
			inversions += query(bit1, 1, pos[j]);
			update(bit1, pos[j], +1);
		}
		
		for (int j = 0; j < i; ++j) {
			//~ cerr << i << " , " << j << " = " << inversions << "\n";
			dp[i] = min(dp[i], dp[j] + inversions);
			inversions -= query(bit1, pos[j + 1] + 1, n) 
			+ query(bit2, pos[j + 1] + 1, n);
			update(bit1, pos[j + 1], -1);
			inversions += query(bit1, 1, pos[j + 1]);
			update(bit2, pos[j + 1], +1);
		}
	}
	cout << dp[n] << "\n";
}

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