Submission #371266

#	Time	Username	Problem	Language	Result	Execution time	Memory
371266		arnold518	Group Photo (JOI21_ho_t3)	C++14	100 / 100	525 ms	640 KiB

Main

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5000;
const ll INF = 1e18;

int N, A[MAXN+10];
ll dp[MAXN+10];

int B[MAXN+10], C[MAXN+10], D[MAXN+10];

struct BIT
{
	ll tree[MAXN+10];
	void init()
	{
		memset(tree, 0, sizeof(tree));
	}
	void update(int i, ll k)
	{
		for(; i<=N; i+=(i&-i)) tree[i]+=k;
	}
	ll query(int i)
	{
		ll ret=0;
		for(; i>0; i-=(i&-i)) ret+=tree[i];
		return ret;
	}
}bit;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);

	for(int i=1; i<=N; i++) dp[i]=INF;
	for(int i=0; i<N; i++)
	{
		for(int j=1, k=i+1; j<=N; j++) if(A[j]>i) B[k++]=A[j];
		for(int j=1; j<=N; j++) C[B[j]]=j, D[j]=0;

		//for(int j=1; j<=N; j++) printf("%d ", B[j]); printf("\n");

		bit.init();
		for(int j=i+1; j<=N; j++)
		{
			D[j]=D[j-1]+bit.query(C[j]);
			bit.update(C[j], 1);
		}
		ll val=0;
		for(int j=N; j>i; j--)
		{
			val+=j;
			val-=C[j];
			D[j-1]+=val;
		}
		for(int j=i+1; j<=N; j++)
		{
			dp[j]=min(dp[j], dp[i]+D[j]);
		}
	}
	printf("%lld\n", dp[N]);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~

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