Submission #629962

#	Time	Username	Problem	Language	Result	Execution time	Memory
629962		QwertyPi	Group Photo (JOI21_ho_t3)	C++14	100 / 100	1024 ms	67520 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 5001;
int h[N];
int h_i[N];
int dp[N][N];
int dp2[N];

struct BIT{
	int bit[N];
	BIT() = default;
	BIT(int n){
		fill(bit, bit + n, 0);
	}
	void clear(int n){
		fill(bit, bit + n, 0);
	}
	void upd(int x, int v){
		for(int i = x; i < N; i = i | (i + 1)){
			bit[i] += v;
		}
	}
	int qry(int x){
		int ret = 0;
		for(int i = x; i >= 0; i = (i & (i + 1)) - 1){
			ret += bit[i];
		}
		return ret;
	}
};

int32_t main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> h[i];
		h_i[h[i]] = i;
	}
	for(int sm = 1; sm <= n; sm++){
		BIT bit(n);
		int cnt;
		
		cnt = 0;
		for(int i = sm; i <= n; i++){
			bit.upd(h_i[i], 1);
		}
		for(int i = sm; i <= n; i++){
			cnt += bit.qry(h_i[i] - 1);
			bit.upd(h_i[i], -1);
			dp[i][sm] = cnt;
		}
		bit.clear(n);
		cnt = 0;
		for(int i = sm; i <= n; i++){
			cnt += bit.qry(h_i[i] - 1);
			bit.upd(h_i[i], 1);
			dp[i][sm] += cnt;
		}

		bit.clear(n);
		cnt = 0;
		for(int i = sm; i <= n; i++){
			cnt += (i - sm) - bit.qry(h_i[i]);
			bit.upd(h_i[i], 1);
			dp[i][sm] -= cnt;
		}
	}
	fill(dp2 + 1, dp2 + n + 1, (1 << 30));
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			dp2[i + 1] = min(dp2[i + 1], dp2[j] + dp[i + 1][j + 1]);
		}
	}
	cout << dp2[n] << endl;
}

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