Submission #290670

#	Time	Username	Problem	Language	Result	Execution time	Memory
290670		tinjyu	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	384 KiB

mountains

#include "mountains.h"
#include <vector>
#include <iostream>
using namespace std;
long long int tag[1005][1005],no,num[1005],tag2[1005];
int maximum_deevs(std::vector<int> y) {
	int n=y.size(),ans=0;
	for(int i=0;i<n;i++)
	{
		int tmp=0;
		double ma=-999999999999;
		for(int j=i-1;j>=0;j--)
		{
			if((double)(y[i]-y[j])/(double)(i-j)>=ma)
			{
				tmp++;
				tag[i][tmp]=j;
				ma=(double)(y[i]-y[j])/(double)(i-j);
			}
		}
		ma=-999999999999;
		for(int j=i+1;j<n;j++)
		{
			if((double)(y[i]-y[j])/(double)(i-j)>=ma)
			{
				tmp++;
				tag[i][tmp]=j;
				ma=(double)(y[i]-y[j])/(double)(i-j);
			}
		}
		num[i]=tmp;
		//cout<<num[i]<<endl;
	}
	while(true)
	{
		long long int mi=99999,p;
		for(int i=0;i<n;i++)
		{
			if(tag2[i]==1)continue;
			if(num[i]<mi)
			{
				mi=num[i];
				p=i;
			}
		}
		if(mi==99999)break;
		ans++;
		tag2[p]=1;
		//cout<<p<<endl;
		for(int i=1;i<=mi;i++)
		{
			tag2[tag[p][i]]=1;
			//cout<<tag[p][i]<<" ";
		}
		//cout<<endl;
	}
	return ans;
}

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