Submission #388505

#	Time	Username	Problem	Language	Result	Execution time	Memory
388505		LucaDantas	Group Photo (JOI21_ho_t3)	C++17	100 / 100	481 ms	67408 KiB

Main

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 5e3+10;

bool mark[maxn];

int a[maxn], val[maxn][maxn], dp[maxn];

int main() {
	int n; scanf("%d", &n);
	int inv = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		for(int j = a[i]+1; j <= n; j++) {
			inv += mark[j];
			val[a[i]][j] += mark[j];
		}
		for(int j = a[i]-1; j >= 1; j--)
			val[j][a[i]] -= mark[j];
		mark[a[i]] = 1;
	}
	for(int sz = 2; sz <= n; sz++) {
		for(int i = 1; i+sz <= n; i++) {
			int j = i + sz;
			val[i][j] += val[i][j-1] + val[i+1][j] - val[i+1][j-1];
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			dp[i] = max(dp[i], val[j][i] + dp[j-1]);
	printf("%d\n", inv - dp[n]);
}

Compilation message (stderr)

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

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