oj.uz

Submission #290666

# Submission time Handle Problem Language Result Execution time Memory
290666 2020-09-04T09:55:31 Z tinjyu Mountains (IOI17_mountains) C++14
0 / 100
 1 ms 384 KB 
#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=9999999999999;
		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;
	}
	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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -