Submission #620850

#	Time	Username	Problem	Language	Result	Execution time	Memory
620850		patrikpavic2	Group Photo (JOI21_ho_t3)	C++17	100 / 100	979 ms	233600 KiB

Main

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 5050;

int n, A[N], P[N][N], inv[N][N], pos[N], dp[N], vec[N][N];

int main(){
	scanf("%d", &n);
	for(int i = 0;i < n;i++){
		scanf("%d", A + i), A[i]--;
		pos[A[i]] = i;
	}
	for(int i = 0;i < n;i++){
		if(i){
			for(int j = 0;j < n;j++)
				P[i][j] = P[i - 1][j];
		}
		for(int j = A[i];j < n;j++)
			P[i][j]++;
	}
	for(int r = 0;r < n;r++){
		inv[r][r] = 0; vec[r][r] = P[pos[r]][n - 1] - P[pos[r]][r];
		for(int l = r - 1;l >= 0;l--){
			inv[l][r] = inv[l + 1][r];
			vec[l][r] = vec[l + 1][r];
			inv[l][r] += P[pos[l]][r] - P[pos[l]][l];
			vec[l][r] += P[pos[l]][n - 1] - P[pos[l]][r];
		}
	}
	for(int i = 0;i < n;i++){
		dp[i] = i * (i + 1) / 2 - inv[0][i] + vec[0][i];
		for(int j = 0;j < i;j++){
			dp[i] = min(dp[i], dp[j] + (i - j) * (i - j - 1) / 2 - inv[j + 1][i] + vec[j + 1][i]);
		}
	}
	printf("%d\n", dp[n - 1]);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", A + i), A[i]--;
      |   ~~~~~^~~~~~~~~~~~~

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