Submission #290671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
290671	2020-09-04T10:02:46 Z	tinjyu	Mountains (IOI17_mountains)	C++14	0 / 100	1 ms	416 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	416 KB	Output is correct
15	Incorrect	1 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	416 KB	Output is correct
15	Incorrect	1 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	416 KB	Output is correct
15	Incorrect	1 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	416 KB	Output is correct
15	Incorrect	1 ms	384 KB	Output isn't correct
16	Halted	0 ms	0 KB	-