Submission #485085

#	Time	Username	Problem	Language	Result	Execution time	Memory
485085		arujbansal	Group Photo (JOI21_ho_t3)	C++17	100 / 100	474 ms	728 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MXN = 2e5 + 5, INF = 1e9 + 5;
int N;
int A[MXN], dp[MXN], pos[MXN];

struct fenwick_tree {
	int n;
	vector<int> tree;

	fenwick_tree(int _n) {
		n = _n;
		tree.assign(n + 1, 0);
	}

	void increment(int pos, int val) {
		for (int i = pos; i <= n; i += i & -i)
			tree[i] += val;
	}

	int query(int pos) {
		int res = 0;

		for (int i = pos; i > 0; i -= i & -i)
			res += tree[i];

		return res;
	}
};

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		dp[i] = INF;
	}

	for (int i = 1; i <= N; i++) {
		// Consider an array of all A[i] <= i, maintain relative positions only - compress
		for (int j = 1, cur_pos = 1; j <= N; j++) {
			if (A[j] <= i)
				pos[A[j]] = cur_pos++;
		}

		fenwick_tree ft(N + 1);

		int cost = 0;
		for (int j = i; j >= 1; j--) {
			int loc = pos[j] - ft.query(pos[j]);
			cost += i - loc - 2 * ft.query(pos[j] - 1);
			ft.increment(pos[j], 1);


			dp[i] = min(dp[i], dp[j - 1] + cost);
		}
	}

	cout << dp[N];
}

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