Submission #652542

#	Time	Username	Problem	Language	Result	Execution time	Memory
652542		ymm	Group Photo (JOI21_ho_t3)	C++17	100 / 100	428 ms	520 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 5010;
int fenp[N], fenn[N];

void add(int i, int x, int fen[])
{
	++i;
	while (i < N) {
		fen[i] += x;
		i += i & -i;
	}
}
int get(int r, int fen[])
{
	int ans = 0;
	while (r > 0) {
		ans += fen[r];
		r -= r & -r;
	}
	return ans;
}

int dp[N];
int pos[N];
int n;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,0,n) {
		int h;
		cin >> h;
		pos[h-1] = i;
	}
	dp[n] = 0;
	LoopR (i,0,n) {
		memset(fenn, 0, sizeof(fenn));
		add(pos[i], 1, fenp);
		int sum = 0;
		dp[i] = 1e9;
		Loop (j,i,n) {
			sum += get(pos[j], fenp) + get(n-pos[j], fenn);
			add(n-pos[j], -1, fenn);
			dp[i] = min(dp[i], dp[j+1] + sum);
		}
	}
	cout << dp[0] << '\n';
}

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