Submission #115778

#	Time	Username	Problem	Language	Result	Execution time	Memory
115778		tinjyu	Meetings (IOI18_meetings)	C++14	0 / 100	808 ms	747036 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();
	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=999999999999;
  		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;
}

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