Submission #1219345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219345		trimkus	Group Photo (JOI21_ho_t3)	C++20	100 / 100	692 ms	596 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 <= MAXN; i += i & -i) {
		bit[i] += delta;
	}
}

ll query(ll* bit, int r) {
	int res = 0;
	for (; 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() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	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] - 1);
			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] - 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: 36 / 36