제출 #1294222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294222		Jawad_Akbar_JJ	Group Photo (JOI21_ho_t3)	C++20	100 / 100	440 ms	134436 KiB

Main

#include <iostream>

using namespace std;
const int N = 5005;
int dp[N], inv[N][N], ext[N][N], ind[N], ft[2][N];

void Add(int t, int i){
	for (; i; i -= i & -i)
		ft[t][i]++;
}

int get(int t, int i, int ans = 0){
	for (; i < N; i += i & -i)
		ans += ft[t][i];
	return ans;
}

int main(){
	int n;
	cin>>n;

	for (int i=1, a;i<=n;i++)
		cin>>a, ind[a] = i, dp[i] = 1e9;

	for (int l=1;l<=n;l++){
		for (int i=1;i<N;i++)
			ft[0][i] = 0;
		for (int r=l;r<=n;r++){
			inv[l][r] = inv[l][r-1] + get(0, n - ind[r] + 1);
			ext[l][r] = ext[l][r-1] + get(1, ind[r]);
			Add(0, n - ind[r] + 1);
		}
		Add(1, ind[l]);
	}

	for (int i=0;i<n;i++){
		for (int j=i+1;j<=n;j++)
			dp[j] = min(dp[j], dp[i] + inv[i+1][j] + ext[i+1][j]);
	}

	cout<<dp[n]<<'\n';
}

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