var
i,j,k,l,n,m:longint;
a:array[0..4000000] of longint;
f,sum,g:array[-1..4000000] of longint;
begin
readln(n,m);
for i:=1 to n do
begin
read(a[i]);
a[i]:=a[i] div 100;
sum[i]:=sum+a[i];
end;
for i:=1 to n do
g[i]:=-1;
k:=m div 100;
f[0]:=m;
if k>=n then
begin
f[n]:=f[0]+(sum[n]-sum[0])*100-n*100;
writeln(f[n]);
exit;
end;
for i:=1 to k do
g[i]:=0;
for i:=1 to n do
begin
f[i]:=f[g[i]]+(sum[i]-sum[g[i]])*100-i*100;
k:=f[i] div 100;
if k>=n then
begin
f[n]:=f[i]+(sum[n]-sum[i])*100-n*100;
writeln(f[n]);
halt;
end;
for j:=k downto i+1 do
if g[j]=-1 then
g[j]:=i
else
break;
end;
writeln(f[n])
end.
清执教
1 条评论
-
东方幻想 LV 8 @ 2014-10-30 20:19:48
给跪了：
const
maxn=2000010;
var
a,f:array[0..maxn]of longint;
n:longint;procedure init;
var
i,x:longint;
begin
read(n,f[0]);
for i:=1 to n do
begin
read(x);
a[i]:=a[i-1]+x;
end;
end;procedure work;
var
i,j:longint;
begin
i:=0;
for j:=1 to n do
begin
while f[i]<j*100 do
inc(i);
f[j]:=f[i]+a[j]-a[i]-j*100;
end;
writeln(f[n]);
end;begin
init;
work;
end.
- 1
信息
- ID
- 1617
- 难度
- 6
- 分类
- 动态规划 | 单调性DP 点击显示
- 标签
- 递交数
- 1855
- 已通过
- 469
- 通过率
- 25%
- 被复制
- 2
- 上传者
-
orz教主_tangky
