Submission #390805

#	Time	Username	Problem	Language	Result	Execution time	Memory
390805		tinjyu	Meetings (IOI18_meetings)	C++14	4 / 100	5519 ms	83140 KiB

meetings

#include "meetings.h"
#include <iostream>
using namespace std;
long long int point[5005][5005][2];
std::vector<long long> minimum_costs(std::vector<int> h, std::vector<int> l, std::vector<int> r) {
	int q = l.size();
	int n = h.size();
	if(n<=5000 && q<=500)
	{
	for(int i=0;i<n;i++)
	{
		int tmp=h[i];
		point[i][i][1]=h[i];
		for(int j=i+1;j<n;j++)
		{
			tmp=max(tmp,h[j]);
			point[i][j][1]=point[i][j-1][1]+tmp;
		}
  	}
  	for(int i=n-1;i>=0;i--)
  	{
  		int tmp=h[i];
  		point[i][i][0]=h[i];
  		for(int j=i-1;j>=0;j--)
  		{
  			tmp=max(tmp,h[j]);
  			 
  			point[j][i][0]=point[j+1][i][0]+tmp;
			//cout<<i<<" "<<j<<" "<<point[j][i][0]<<"  ";
		}
		//cout<<endl;
	}
  	std::vector<long long> c(q);
  	for(int i=0;i<q;i++)
  	{
  		long long int tmp=999999999999999999;
  		for(int j=l[i];j<=r[i];j++)
  		{
  			if(point[l[i]][j][0]+point[j][r[i]][1]-h[j]<tmp)
  			{
  				c[i]=j;
  				tmp=point[l[i]][j][0]+point[j][r[i]][1]-h[j];
				//cout<<tmp<<" "<<j<<" "<<point[l[i]][j][0]<<" "<<point[j][r[i]][1]<<"  ";
			}
		}
		c[i]=tmp;
		//cout<<endl;
	}
	return c;
	}
	else
	{
		std::vector<long long> c(q);
		for(int i=0;i<q;i++)
		{
			long long int len=0,now=0;
			for(int j=l[i];j<=r[i];j++)
			{
				if(h[j]==1)now++;
				else
				{
					len=max(len,now);
					now=0;
				}
			}
			len=max(len,now);
			c[i]=(r[i]-l[i]+1)*2-len;
		}
		return c;
	}
	
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40