제출 #92717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92717		MRtoma	Money (IZhO17_money)	C++14	0 / 100	2 ms	376 KiB

money

#include<bits/stdc++.h>
#define f first
#define s second
#define inf 999999999999
#define N  1000009
#define M  (L+R)/2
#define ll long long
#define pb push_back
using namespace std;

ll n,a[N],i,j,ans,sum,b[N],fix[N],dp[N];

pair <ll, ll> S[N];

set <ll> s;
set <ll>::iterator it;

int main()
{

	ios::sync_with_stdio(0);
	
	cin>>n;
	
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		s.insert(a[i]);
	}
	
	s.insert(inf);
	
	for(i=1;i<=n;i++)
	{
		it=s.upper_bound(a[i]);
		fix[i]=*it;
	}
	
	ans=n;
	
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				sum=inf; bool ok=false;
				for(int i1=i;i1<j;i1++)
				{
					if(a[i1]>a[i1+1]){ok=true;break;}		
				}
				if(ok)continue;
				sum=n-j+i;
				for(int i1=1;i1<i-1;i1++)
				{
					if(fix[a[i1]]<=a[i1+1])sum--;		
				}
				
			
				for(int i1=j+1;i1<n;i1++)
				{
					if(fix[a[i1]]<=a[i1+1])sum--;		
				}
				
				if(ans>sum)ans=sum;
			//	cout<<sum<<" "<<i<<" "<<j<<endl;
			}
		}
cout<<ans<<endl;
return 0;
}

/*
6
3 6 4 5 1 2
*/

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55