Submission #411702

#	Time	Username	Problem	Language	Result	Execution time	Memory
411702		nxteru	Mountains (IOI17_mountains)	C++14	20 / 100	1089 ms	296 KiB

mountains

#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int>y;
int solve(int l,int r){
	if(r<l)return 0;
	if(l==r)return 1;
	int ma=-1;
	for(int i=l;i<=r;i++){
		if(ma==-1||y[ma]<y[i])ma=i;
	}
	int s=1;
	int la=ma;
	for(int i=ma-1;i>=l;i--){
		if(ll(y[ma]-y[i])*ll(ma-la)<=ll(y[ma]-y[la])*ll(ma-i)){
			s+=solve(i+1,la-1);
			la=i;
		}
	}
	s+=solve(l,la-1);
	la=ma;
	for(int i=ma+1;i<=r;i++){
		if(ll(y[ma]-y[i])*ll(ma-la)>=ll(y[ma]-y[la])*ll(ma-i)){
			s+=solve(la+1,i-1);
			la=i;
		}
	}
	s+=solve(la+1,r);
	return max(s,solve(l,ma-1)+solve(ma+1,r));
}
int maximum_deevs(vector<int> Y) {
	y=Y;
	return solve(0,y.size()-1);
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30