Submission #372223

#	Time	Username	Problem	Language	Result	Execution time	Memory
372223		dolphingarlic	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1100 ms	752 KiB

Main

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

int n, pos[5001], dp[5001], bit1[5001], bit2[5001];

void update(int *bit, int pos, int val) {
	for (; pos <= n; pos += pos & -pos) bit[pos] += val;
}
int query(int *bit, int a, int b) {
	int ans = 0;
	for (; b; b -= b & -b) ans += bit[b];
	for (a--; a; a -= a & -a) ans -= bit[a];
	return ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		pos[a] = i;
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = INT_MAX;

		// First, get inversions from [1; i]
		int inversions = 0;
		for (int j = 1; j <= i; j++) {
			inversions += query(bit1, 1, pos[j] - 1);
			update(bit1, pos[j], 1);
		}

		// Then find the best j for dp[i]
		memset(bit2, 0, sizeof bit2);
		for (int j = 0; j < i; j++) {
			dp[i] = min(dp[i], dp[j] + inversions);
			// First, remove j + 1 from bit1 and subtract its contribution
			inversions -= query(bit1, pos[j + 1] + 1, n) + query(bit2, pos[j + 1] + 1, n);
			update(bit1, pos[j + 1], -1);
			// Next, add j + 1 to bit2
			inversions += query(bit1, 1, pos[j + 1] - 1);
			update(bit2, pos[j + 1], 1);
		}
	}
	cout << dp[n];
	return 0;
}

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