Submission #643343

#	Time	Username	Problem	Language	Result	Execution time	Memory
643343		Augustyn	Group Photo (JOI21_ho_t3)	C++14	100 / 100	395 ms	196676 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n,h[5001],gdzie[5001];
int dp[5011],ilewiek[5011][5011],ilemn[5011][5011];
int czynap(int a,int b)
{
	if(gdzie[a]<gdzie[b])
		return 1;
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&h[i]);
		gdzie[h[i]]=i;
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=n;j>i;--j)
			ilewiek[i][j]=ilewiek[i][j+1]+czynap(j,i);
		for(int j=i;j>0;--j)
			ilemn[i][j]=ilemn[i][j+1]+czynap(j,i);
		ilemn[i][0]+=ilemn[i][1];
		for(int j=i;j>=0;--j)
			ilewiek[i][j]+=ilewiek[i][j+1];
	}
	for(int i=n;i>=0;--i)
	{
		for(int j=n;j>=0;--j)
			ilewiek[i][j]+=ilewiek[i+1][j];
		for(int j=n;j>=0;--j)
			ilemn[i][j]+=ilemn[i+1][j];
	}
	for(int i=1;i<=n;++i)
	{
		dp[i]=INT_MAX; 
		for(int j=1;j<=i;++j)
		{
			dp[i]=min(dp[i],dp[j-1]+ilewiek[j][i+1]-ilewiek[i+1][i+1]+ilemn[j][j]-ilemn[i+1][j]);
		}
	}
	printf("%d",dp[n]);
	return 0;
}

Compilation message (stderr)

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

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