don't use brute force... O(n^2) n=30000 ===>>> time limit)

hint: you can don't use N in your solution

it is incorrect test

The sum of all elements of the sequence must be equal to S + N (60000). Your test is incorrect.

program Project286286;

{$APPTYPE CONSOLE}

uses
  SysUtils,Math;



var a,b,c:array[0..2000000]of longint;
i,j,m,n,f:longint;

function RMQ(l,r:longint):longint;
var res,i,j:longint;
begin
 i := l + n - 1;
 j := r + n - 1;
 res:=0;
 while i<=j do
   begin
     res := max(res,max(a[i],a[j]));
     i:=(i+1) div 2;
     j:=(j-1) div 2
   end;
 result:=res;
end;


begin
 reset(input,'input.txt');
 rewrite(output,'output.txt');
 readln(n);
 for i := 1 to n do
   readln(c[i]);
 for i := 1 to n do
   c[i]:=c[i]-1+c[i-1];
 for i := 1 to n do
   b[i]:=c[i]-c[i-1];
 for i := n to 2*n-1 do
   a[i]:=b[i-n+1];
 for i := n-1 downto 1 do
   a[i]:= max(a[i*2],a[i*2+1]);
 for i := 1 to n - 1 do
   if rmq(i+1,n)-c[i-1]>n then
     begin
       writeln('NO');
       halt(0);
     end;
 writeln('YES');
end.

probably if you subtract 1 from every element, you get simpler problem.

"No" is true.

because: a[1]=1 a[2]=3 a[3]=0 a[4]=3 a[5]=0;

sum=a[1]+a[2]+a[3]=6 > (4-2+1)+2=5 ,=> "No"

Think about simpler solution -> without array - just O(n) !!

var sum,s,n,i,j,k:longint; a:array[1..30000]of longint;
begin
read(s,n);
for i:=1 to s do read(a[i]);
for j:=1 to s do
for i:=1 to j do
begin sum:=0;
for k:=i to j do sum:=sum+a[k];
if sum>j-i+n+1 then begin write('NO'); exit; end;
end;
write('YES');
end.

var sum,s,n,i,j,k:longint; a:array[1..30000]of longint;
begin
read(s,n);
for i:=1 to s do read(a[i]);
for j:=1 to s do
for i:=1 to j do
begin sum:=0;
for k:=i to j do sum:=sum+a[k];
if sum>j-i+n+1 then begin write('NO'); exit; end;
end;
write('YES');
end.

I don't understand a problem

Why the answer to sample input 1 is "YES" ?
If we take i = 2 and j = 3, then
(3+0)<>(3-2+1)+3

Admins! I'm also sure that in test4 sum of all Ai is not equal to S+N !!! I just calculated the sum and if it was not equal to S+N I thrown the exception ("throw 0;"). And I got Crash on test4 !
Please, check test4!

it has to ba int A[30001] not int A[30000]

just try it

Edited by author 23.07.2004 04:20

Edited by author 23.07.2004 04:20

It should be Ai + Ai+1 + ... + Aj.

Just think when it is most likely the inequality won't be true ! When
You realize it You'll get AC !