蒟蒻70pts,WA on #4,5,6,求助大佬
查看原帖
蒟蒻70pts,WA on #4,5,6,求助大佬
615438
jpjpjpjp楼主2024/8/9 20:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=500005;
struct s
{
	int w,l;
}num[maxn],a[maxn];
int n,tot=0,dp[maxn];
bool cmp(s a,s b)
{
	if(a.w==b.w)return a.l<b.l;
	return a.w<b.w;
}
int q[maxn],head=1,tail=0;
inline int X(int id){return a[id+1].l;}
inline int Y(int id){return dp[id];}
inline long double slope(int id1,int id2){return (Y(id1)-Y(id2))*(long double)1.0/(X(id2)-X(id1));}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&num[i].w,&num[i].l);
	sort(num+1,num+n+1,cmp);
	tot=1;
	for(int i=1;i<=n;i++)
	{
		if(a[tot].l>num[i].l)a[++tot]=num[i];
		else a[tot]=num[i];
	}
//	for(int i=1;i<=tot;i++)
//		cout<<a[i].l<<" ";
//	cout<<endl;
//	for(int i=1;i<=tot;i++)
//		cout<<a[i].w<<" ";
//	cout<<endl;
	q[++tail]=0;
	for(int i=1;i<=tot;i++)
	{
		int k=a[i].w;
		while(head<tail&&slope(q[head],q[head+1])<=k)head++;
		dp[i]=Y(q[head])+k*X(q[head]);
		while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i))tail--;
		q[++tail]=i;
	}
	printf("%lld",dp[tot]);
	return 0;
}
2024/8/9 20:58
加载中...