P2900 [USACO08MAR]Land Acquisition G

样例没过 查了一小时 感觉没写错。。。

#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template <typename T>
inline T Read(T Type)
{
	T x = 0,f = 1;
	char a = getchar();
	while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
	while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
	return x * f;
}
const int MAXN = 5e4 + 5;
typedef long long ll;
//#define getk(i,j) (1.0*getup(i,j)/getdown(i,j))
//l长,w宽
int n,q[MAXN],head,tail = 1;
ll dp[MAXN];
stack<int> tp; 
pair<int,int> soil[MAXN],pre[MAXN];
inline ll getup(int j,int k) {return dp[j] - dp[k];}
inline ll getdown(int j,int k) {return pre[j + 1].second - pre[k + 1].second;}
inline ll getdp(int i,int j) {return dp[j] + pre[j + 1].second * pre[i].first;}
int main()
{
	n = Read(1);
	for(reg i = 1;i <= n;i++)
		soil[i].first = Read(1),soil[i].second = Read(1);
	sort(soil + 1,soil + 1 + n);//从小到大 
	for(reg i = 1;i <= n;i++) {while(!tp.empty()&&soil[i].second >= soil[tp.top()].second) tp.pop();tp.push(i);}
	int cnt = tp.size(),Q = 0;
	while(!tp.empty()) pre[cnt - Q++] = soil[tp.top()],tp.pop();
	for(reg i = 1;i <= cnt;i++)
	{
		while(head + 1 < tail&&getup(q[head + 1],q[head]) >= pre[i].first * getdown(q[head + 1],q[head])) head++;
		dp[i] = getdp(i,q[head]);
		while(head + 1 < tail&&getup(q[tail - 1],q[tail - 2]) * getdown(i,q[tail - 1]) <= getup(i,q[tail - 1]) * getdown(q[tail - 1],q[tail - 2])) tail--;
		q[tail++] = i;
	}
	printf("%lld",dp[cnt]);
	return 0;
}