调整答案不要用while调整。

……看到这道题就想到mint

目测图已被管理员内部掉了 (*/ω╲*)

= =

我以后再也不用眼看数据范围了，直接复制。

%%%%

%%%
先来个n2水一水
不过怎么全T了

倍增666

反白查看做这题的重要结论。
只需要考虑一条直径

23333
%%%

选了8个素数...压力略大......

不会写Floyd只会写Dijs不用考虑重边

#include<cstdio>
#include<cmath>
#include<algorithm>
#define precision 0.0001
#define maxn 1000
using namespace std;
struct tnode{double d,p;}a[maxn+10];
double d1,c,d2,p;
int n;
bool cmp(tnode xx,tnode yy)
{
return xx.d<yy.d;
}
int main()
{
// freopen("lyuxing.in","r",stdin);
// freopen("lyuxing.out","w",stdout);
int i,j,k; double s,ans,x,y;
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n);
a[1].d=0,a[1].p=p;
a[2].d=d1,a[2].p=0;
for(n+=2,i=3;i<=n;i++)scanf("%lf%lf",&a[i].d,&a[i].p);
sort(a+1,a+n+1,cmp);
k=1,ans=x=0,s=c*d2;
while(k<=n)
{
if(a[k+1].d-a[k].d>s){printf("No Solution\n");return 0;}
for(j=k+1;a[j].d-a[k].d<=s && j<=n;j++)
if(a[j].p<=a[k].p)
{
y=(a[j].d-a[k].d)/d2;
if(x<y)ans+=a[k].p*(y-x),x=0;
else x-=y;
k=j;
break;
}
if(fabs(a[k].d-d1)<=precision)
{
printf("%.2lf\n",ans);
return 0;
}
if(j!=k)
{
ans+=a[k].p*(c-x);
x=c-(a[k+1].d-a[k].d)/d2;
k++;
}
}
return 0;
}

回复 @name :
哥们你是可以重评的，不必交这么多遍...

坑正确率的题目。。。

用dfs写了个离线动态生成树，结果看别人的代码都是在线暴力并查集= =

Orz..这模型厉害。。。

神一般的位运算……然而还是没有完全参透，明天一定再看看……