Submission #1089806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089806		peacebringer1667	Group Photo (JOI21_ho_t3)	C++17	100 / 100	269 ms	137328 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 5e3 + 5;
const int inf = 1e9;

int rev[maxn][maxn],inv[maxn][maxn],dp[maxn],a[maxn],pos[maxn],pre[maxn];

void prepare_rev(int n){
	for (int i = 1 ; i < n ; i++)
	  for (int j = i + 1 ; j <= n ; j++)
	    if (a[i] < a[j])
	    	rev[a[i]][a[j]]++;
	
	for (int len = 3 ; len <= n ; len++)
	  for (int i = 1 ; i <= n - len + 1 ; i++){
	  	int l = i,r = i + len - 1;
	  	rev[l][r] += rev[l + 1][r] + rev[l][r - 1] - rev[l + 1][r - 1];
	  }
}

void prep_inv(int L,int n){
	for (int i = n ; i > 0 ; i--)
		pre[i] = pre[i + 1] + (a[i] < L);
	
	int tmp = 0;
	for (int R = L ; R <= n ; R++){
		tmp += pre[pos[R]];
		inv[L][R] += tmp;
	}
}

void prepare_inv(int n){
	for (int L = 1 ; L <= n ; L++){
		for (int i = 1 ; i <= n ; i++) pre[i] = 0;
		prep_inv(L,n);
	}
}

void refresh(int n){
	for (int i = 2 ; i <= n ; i++) dp[i] = inf;
}

int solve(int n){
	for (int i = 1 ; i <= n ; i++){
		for (int j = i ; j > 0 ; j--)
		  dp[i] = min(dp[i],dp[j - 1] + rev[j][i] + inv[j][i]);
	}
	return dp[n];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
		pos[a[i]] = i;
	}
	
	prepare_rev(n);
	prepare_inv(n);
	refresh(n);
	
	cout << solve(n);

	return 0;
}

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