Submission #526465

#	Time	Username	Problem	Language	Result	Execution time	Memory
526465		mosiashvililuka	Money (IZhO17_money)	C++14	45 / 100	1529 ms	5532 KiB

money

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],dp[1000009],g[1000009];
map <int, int> m;
map <int, int>::iterator it;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++) cin>>f[i];
	dp[0]=0;
	for(i=1; i<=a; i++){
		dp[i]=i;
		for(j=i-1; j>=0; j--){
			for(jj=j; jj>=1; jj--){
				if(f[jj]>f[j+1]&&f[jj]<f[i]) break;
			}
			if(jj==0){
				dp[i]=min(dp[i],dp[j]+1);
			}
			if(f[j]>f[j+1]) break;
		}
	}
	cout<<dp[a];
	return 0;
}

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