F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:本站提供各级各类比赛模拟题,有意者请联系本站邮箱Lydsy2012@163.com,欢迎各校教练、老师、家长来信咨询,非诚勿扰。
大视野在线测评-欢迎您
[ New Thread ]
Problem 2153 >> 哪位大佬能帮我看看代码哪里错了吗
chanyeol @ 2019-07-11 21:08:07
[ Quote ] [ Edit ] [ Delete ] 1#
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=40010;
int n;
long long sumt[maxn],sumr[maxn],m;
long long f[maxn];
int q[maxn];
int head=1,tail=1;
template<class T>
void read(T &x)
{
bool f=0;char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
if(f) x=-x;
}
struct Node
{
long long r,t;
}a[maxn];
bool cmp(Node a,Node b)
{
return a.t>b.t;
}
long long get_f(int i,int j)
{
return f[j]+sumt[i]-sumt[j]-a[i].t*(sumr[i]-sumr[j]);
}
double slope(int i,int j)
{
double x1=sumr[i],y1=f[i]-sumt[i];
double x2=sumr[j],y2=f[j]-sumr[j];
return (y2-y1)/(x2-x1);
}
int main()
{
read(n);
read(m);
for(int i=1;i<=n;i++)
{
read(a[i].t);read(a[i].r);
}
sort(a+1,a+n+1,cmp);
a[n+1].t=a[n+1].r=0;
for(int i=1;i<=n+1;i++)
{
sumt[i]=sumt[i-1]+a[i].t*a[i].r;
}
for(int i=1;i<=n+1;i++)
{
sumr[i]=sumr[i-1]+a[i].r;
}
q[1]=0;
head=tail=1;
for(int i=1;i<=n+1;i++)
{
for(;(head<tail)&&(get_f(i,q[head])>=get_f(i,q[head+1]));head++);
f[i]=get_f(i,q[head]);
if(i!=n+1)
{
f[i]+=m;
}
for(;(head<tail)&&(slope(i,q[tail])<slope(i,q[tail-1]));tail--);
q[++tail]=i;
}
printf("%lld\n",f[n+1]);
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back