Submission #388516

#	Time	Username	Problem	Language	Result	Execution time	Memory
388516		luciocf	Group Photo (JOI21_ho_t3)	C++14	100 / 100	922 ms	67552 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e3+10;
const int inf = 1e9+10;

struct FenwickTree
{
	int bit[maxn];

	void upd(int x, int v)
	{
		for (; x < maxn; x += (x&-x))
			bit[x] += v;
	}

	int soma(int x)
	{
		int ans = 0;
		for (; x > 0; x -= (x&-x))
			ans += bit[x];
		return ans;
	}

	int get(int l, int r)
	{
		if (l > r) return 0;
		return soma(r) - soma(l-1);
	}
} BIT[2];

int a[maxn];
int val[maxn][maxn];

int dp[maxn];

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);

		a[x] = i;
	}

	for (int l = 1; l <= n; l++)
	{
		memset(BIT[0].bit, 0, sizeof BIT[0].bit);
		memset(BIT[1].bit, 0, sizeof BIT[1].bit);

		for (int i = l; i <= n; i++)
			BIT[0].upd(a[i], 1);

		for (int r = l; r <= n; r++)
		{
			val[l][r] = val[l][r-1];
			val[l][r] -= BIT[1].get(a[r]+1, n);
			val[l][r] += BIT[0].get(1, a[r]-1);

			BIT[1].upd(a[r], 1);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		dp[i] = inf;

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

	printf("%d\n", dp[n]);
}

Compilation message (stderr)

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

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