记录编号	83534	评测结果	AAAAAAAAWT
题目名称	越低越买	最终得分	80
用户昵称	ranto	是否通过	未通过
代码语言	C++	运行时间	1.628 s
提交时间	2013-12-03 21:27:53	内存使用	8.00 MiB

#include <fstream>
#include <vector>
#include <string>
#include <set>

using namespace std;

ifstream in("buylow.in");
ofstream out("buylow.out");

class INT
{
public:
	int size;
	int num[200];
	INT(unsigned long long u=0) : size(1)
	{
		/*for(int i=0;i!=200;++i)
		{
			num[i]=0;
		}*/
		int i(0);
		while(u)
		{
			num[i]=u%10;
			u/=10;
			++i;
			++size;
		}
	}
	INT(std::string &str)
	{
		size=str.size();
		int j(0);
		for(int i=str.size()-1;i!=-1;++i)
		{
			num[j]=str[i]-48;
		}
		/*for(int i=0;i!=200;++i)
		{
			num[i]=0;
		}*/
	}
	INT &operator=(unsigned long long u)
	{
		/*for(int i=0;i!=200;++i)
		{
			num[i]=0;
		}*/
		int i(0);
		while(u)
		{
			num[i]=u%10;
			u/=10;
			++i;
			++size;
		}
		if(size>1)
		{
			--size;
		}
		return *this;
	}
	INT &operator=(INT rh)
	{
		size=rh.size;
		for(int i=0;i!=size;++i)
		{
			num[i]=rh[i];
		}
		return *this;
	}
	inline int &operator[](int a)
	{
		return num[a];
	}
};

istream &operator>>(istream &_in, INT &a)
{
	string str;
	_in>>str;
	a.size=str.size();
	int j(0);
	for(int i=0;i!=200;++i)
	{
		a.num[i]=0;
	}
	for(int i=str.size()-1;i!=-1;--i)
	{
		a[j]=str[i]-48;
		++j;
	}
	return _in;
}

ostream &operator<<(ostream &_out, INT &a)
{
	for(int i=a.size-1;i!=-1;--i)
	{
		_out<<a[i];
	}
	return _out;
}

INT operator+(INT &rh, INT &lh)
{
	INT ret;
	int size(max(rh.size,lh.size));
	ret[size]=0;
	for(int i=0;i!=size;++i)
	{
		ret[i]=rh[i]+lh[i];
	}
	for(int i=0;i!=size;++i)
	{
		if(ret[i]>9)
		{
			int itemp(ret[i]/10);
			ret[i]%=10;
			ret[i+1]+=itemp;
		}
	}
	ret.size=size;
	if(ret[size]>0)
	{
		++ret.size;
	}
	return ret;
}

bool operator<(INT rh, INT lh)
{
	if(rh.size<lh.size)
	{
		return true;
	}
	else if(rh.size>lh.size)
	{
		return false;
	}
	for(int i=rh.size-1;i!=-1;--i)
	{
		if(rh[i]<lh[i])
		{
			return true;
		}
		else if(rh[i]>lh[i])
		{
			return false;
		}
	}
	return false;
}

bool operator>(INT rh, INT lh)
{
	if(rh.size<lh.size)
	{
		return false;
	}
	else if(rh.size>lh.size)
	{
		return true;
	}
	for(int i=rh.size-1;i!=-1;--i)
	{
		if(rh[i]<lh[i])
		{
			return false;
		}
		else if(rh[i]>lh[i])
		{
			return true;
		}
	}
	return false;
}

bool operator==(INT &rh, INT &lh)
{
	if(rh.size<lh.size)
	{
		return false;
	}
	else if(rh.size>lh.size)
	{
		return false;
	}
	for(int i=rh.size-1;i!=-1;--i)
	{
		if(rh[i]<lh[i])
		{
			return false;
		}
		else if(rh[i]>lh[i])
		{
			return false;
		}
	}
	return true;
}

int n;
INT money[5001];
int f[5001];
INT g[5001];
int resf(0);
INT resg(0);

int main()
{
	in>> n;
	if(n==1)
	{
		out<< 1<< ' '<< 1<< endl;
		return 0;
	}
	for(int i=0; i!=n; ++i)
	{
		in>> money[i];
		f[i]=1;
		g[i]=0;
	}
	g[0]=1;
	INT imax(0);
	for(int i=1; i!=n; ++i)
	{
		if(money[i]>imax||money[i]==imax)
		{
			imax=money[i];
			g[i]=1;
		}
		int mlen(0);
		for(int j=0; j!=i; ++j)
		{
			if(money[i]<money[j] )
			{
				if(f[i]<f[j]+1)
				{
					f[i]=f[j]+1;
					mlen=f[j];
				}
			}
		}
		set<INT> iset;
		for(int j=0; j!=i; ++j)
		{
			if(f[j]==mlen&&money[j]>money[i]&&iset.find(money[j] )==iset.end() )
			{
				iset.insert(money[j] );
				g[i]=g[i]+g[j];
			}
		}
		if(f[i]>resf)
		{
			resf=f[i];
		}
	}
	/*for(int i=0; i!=n; ++i)
	{
		out<< f[i]<< ' ';
	}
	out<< endl;
	for(int i=0; i!=n; ++i)
	{
		out<< g[i]<< ' ';
	}
	out<< endl;*/
	set<INT> iset;
	for(int i=n-1; i!=-1; --i)
	{
		if(f[i]==resf&&iset.find(money[i] )==iset.end() )
		{
			iset.insert(money[i] );
			resg=resg+g[i];
		}
	}
	out<< resf<< ' '<< resg<< endl;
	return 0;
}