milk2.cpp

USACO chapter one.May hope it useful to someone

/*
ID: chenkai4
PROG: milk2
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("milk2.in");
ofstream out("milk2.out");
int maxIdle=0,maxWork,N;
int begin[5002],end[5002],daynum=1;
int t;
#define mid(A) ((end[A]+begin[A])/2)
#define min(A,B) (A<B?A:B)
#define max(A,B) (A>B?A:B)
bool beIn(int i1,int i2)
{
	if(mid(i1)>mid(i2))
	{t=i1;i1=i2;i2=t;}
	if(end[i1]-mid(i1)+mid(i2)-begin[i2]>=mid(i2)-mid(i1)||(end[i1]+1==begin[i2])||(end[i2]+1==begin[i1]))
		return true;
	return false;
}
int main()
{
	in>>N;
	in>> begin[1]>>end[1];
	for(int a=2;a<=N;a++)
	{
		in>>begin[daynum+1]>>end[daynum+1];
		for(int b=daynum;b>=1;b--)
		{
			if(beIn(b,daynum+1))
			{
				begin[b]=min(begin[daynum+1],begin[b]);begin[daynum+1]=0;
				end[b]=max(end[daynum+1],end[b]);end[daynum+1]=0;
			}
		}
		if(begin[daynum+1]!=0)
			daynum++;
	}
	for(int a=1;a<daynum;a++)
		for(int b=a+1;b<=daynum;b++)
			if(begin[b]<begin[a])
			{
				t=begin[a];begin[a]=begin[b];begin[b]=t;
				t=end[a];end[a]=end[b];end[b]=t;
			}
	maxWork=end[1]-begin[1];
	for(int a=2;a<=daynum;a++)
	{
		if(begin[a]-end[a-1]>maxIdle)
			maxIdle=begin[a]-end[a-1];
		if(end[a]-begin[a]>maxWork)
			maxWork=end[a]-begin[a];
	}
	out<<maxWork<<" "<<maxIdle<<endl;
	return 0;
}