比赛 |
20090916练习赛 |
评测结果 |
AWAWWAAAAA |
题目名称 |
护卫队 |
最终得分 |
70 |
用户昵称 |
Truth.Cirno |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-10-17 20:28:35 |
显示代码纯文本
#include <cstdio>
using namespace std;
double arrmax(double a[],int l,int r)
{
int i;
double minnum=-1;
for (i=l;i<=r;i++)
if (minnum<a[i])
minnum=a[i];
return(minnum);
}
int main(void)
{
freopen("convoy.in","r",stdin);
freopen("convoy.out","w",stdout);
const int MAXINT=1000000000;
int i,j,maxwei,maxlen,n,wei[1000]={0},weisum[1000]={0},temp;
double ftemp,tim[1000]={0},f[1000]={0};
scanf("%d %d %d",&maxwei,&maxlen,&n);
for (i=1;i<=n;i++)
{
scanf("%d %d",&wei[i],&temp);
weisum[i]=weisum[i-1]+wei[i];
tim[i]=double(maxlen)/double(temp)*60.0;
f[i]=MAXINT;
}
temp=0;
i=1;
while (i<=n)
{
for (j=temp;j<=i-1;j++)
{
ftemp=arrmax(tim,j+1,i)+f[j];
if (f[i]>ftemp)
f[i]=ftemp;
}
i++;
while (weisum[i]-weisum[temp]>maxwei)
temp++;
}
printf("%.1lf\n",f[n]);
fclose(stdin);
fclose(stdout);
return(0);
}