Submission #916743

#	Time	Username	Problem	Language	Result	Execution time	Memory
916743		NintsiChkhaidze	Group Photo (JOI21_ho_t3)	C++17	100 / 100	633 ms	196024 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define pii pair <int,int>
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define int ll 
using namespace std;

const int N = 5e3 + 3,inf = 1e18;

int a[N],dp[N],id[N],val[N],pr[N];
int fen[N],D[N][N];

void upd(int idx,int dl){
	while (idx <= 5000){
		fen[idx] += dl;
		idx += (idx & (-idx));
	}
}

int get(int idx){
	int s=0;
	while (idx>0){
		s += fen[idx];
		idx -= (idx & (-idx));
	}
	return s;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n;
	cin>>n;

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

	for (int i = 1; i <= n; i++){
		int s = 0;
		for (int l = i; l >= 1; l--){
			upd(id[l],1);
			s += (i - l + 1) - get(id[l]);
			D[l][i] = s;
		}

		for (int l = i; l >= 1; l--)
			upd(id[l],-1);

		int c=0;
		for (int j = 1; j <= n; j++){
			if (a[j] > i) ++c;
			val[j] = c; 
		}

		for (int j = 1; j <= n; j++){
			pr[j] = pr[j - 1] + val[id[j]];
		}

		for (int j = 1; j <= i; j++){
			dp[i] = min(dp[i],dp[i - j] + pr[i] - pr[i - j] + D[i - j + 1][i]);
		}
	}

	cout<<dp[n];
}

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