Submission #373071

#	Time	Username	Problem	Language	Result	Execution time	Memory
373071		GioChkhaidze	Group Photo (JOI21_ho_t3)	C++14	100 / 100	417 ms	134656 KiB

Main

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 5005;

int n, q, a[N], inv[N][N], invr[N][N], S[N], Dp[N];

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= n; ++i) {
		for (int j = a[i]; j <= n; ++j) {
			++S[j];
		}	
		
		for (int x = a[i] + 1; x <= n; ++x) {
			inv[a[i]][x] = S[n] - S[x - 1];
			invr[a[i]][x] = (x - a[i]) - (S[x] - S[a[i]]);
		}
	}

	ll U;
	for (int r = 1; r <= n; ++r) {
		Dp[r] = 1e9, U = 0;
		for (int l = r; l >= 1; --l) {
			U += inv[l][r + 1] + invr[l][r];
			if (Dp[r] > Dp[l - 1] + U)
				Dp[r] = Dp[l - 1] + U;
		}
	}
	
	cout << Dp[n] << "\n";
}

Compilation message (stderr)

Main.cpp:11:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main () {
      |       ^

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