Cod sursa(job #254679)
Utilizator | Data | 7 februarie 2009 13:42:01 | |
---|---|---|---|
Problema | Cuburi2 | Scor | 20 |
Compilator | fpc | Status | done |
Runda | Stelele Informaticii 2009, clasele 9-10, ziua 2 | Marime | 2.08 kb |
program alex;
var f,g:text;
t:array[1..250005]of longint;
i,j,x,y,h,m,n,turn,d,mij,a,b:longint;
s,min,s1:int64;
begin
assign(g,'cuburi2.out');rewrite(g);
assign(f,'cuburi2.in');reset(f);
readln(f,n,m);
for i:=1 to n do
read(f,t[i]);
readln(f);
if n<=5000 then begin
for i:=1 to m do
begin
readln(f,x,y);
min:=90000000000000000;
for j:=x to y do
begin
s:=0;
for h:=x to j-1 do
s:=s+t[h]*(j-h);
d:=0;
for h:=j+1 to y do
begin
d:=d+1;
s:=s+t[h]*d;
end;
if s<min then begin
turn:=j;
min:=s;
end;
end;
writeln(g,turn,' ',min);
end;
end
else begin
for i:=1 to m do
begin
min:=90000000000000000;
readln(f,x,y);
a:=x;
b:=y;
mij:=(a+b)div 2;
while a<=b do
begin
s:=0;
for j:=x to mij-1 do
s:=s+t[j]*(mij-j);
d:=0;
s1:=0;
for j:=mij+1 to y do
begin
d:=d+1;
s1:=s1+t[j]*d;
end;
if s+s1<min then begin
turn:=mij;
min:=s+s1;
end;
if s<s1 then begin
a:=mij+1;
mij:=(a+b)div 2;
end
else begin
b:=mij-1;
mij:=(a+b)div 2;
end;
end;
writeln(g,turn,' ',min);
end;
end;
close(f);
close(g);
end.