oj.uz

답안 #92719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92719 2019-01-04T11:22:28 Z MRtoma Money (IZhO17_money) C++14
0 / 100
 2 ms 376 KB 
#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;
				if(sum==1){
					cout<<0<<endl;
					return 0;
				}
				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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -