The property holds for all (i,j) if and only if it holds for all prefixes and all suffixes. You can prove this easily with pen and paper. Prefix and suffix sums can be checked in linear time. Subtract 1 from each element Apply window to the array for max sum of S #include <bits/stdc++.h> using namespace std; #define repl(i,x,n) for(long long i=(long long)(x);i<(long long)(n);i++) #define rep(i,x,n) for(long i=long(x);i<long(n);i++) int main() { //ifstream cin("input.in"); //ofstream cout("output.out"); ios::sync_with_stdio(0);cin.tie(0); long n,s,a[100009],p=0; cin>>n>>s; bool flag=1; rep(i,0,n) { cin>>a[i]; a[i]--; } rep(i,0,n) { p+=a[i]; if(p>s) flag=0; p=max(p,0l); } if(flag) cout<<"YES"; else cout<<"NO"; } Edited by author 11.12.2017 08:23 Так как сумма всех элементов последовательности равна (S+N), то сумма всех элементов последовательности, в которой каждый элемент уменьшен на единицу, равна просто N. Тогда если мы найдём в такой последовательности с уменьшенными членами отрезок с максимальной суммой и сравним сумму на нем с числом N, то мы узнаем ответ на задачу. А именно, если эта сумма превосходит N, то ответ "NO". В противном случае, ответ "YES". Отрезок с максимальной суммой ищется за O(n) методом кумулятивных сумм. used: ... for(i=1;i<=S;i++) for(j=i;j<=S;j++) ... But the result is 'Time limit exceeded'. Please help, why 'Time limit exceeded'? don't use brute force... O(n^2) n=30000 ===>>> time limit) hint: you can don't use N in your solution brute force (with some optimizations) works fine input: 6 10 2 2 2 0 10 1 output: NO substract one from every element of sequence and search for prefix or suffix (I mean subsequence A_0, A_1, ..., A_j or A_k, A_{k+1}, ..., A_s) with negative sum. 30000 30000 0 | 0 | . | => 30000 lines with '0' on each . | 0 | There are solutions that may get Time Limit. The sum of all elements of the sequence must be equal to S + N (60000). Your test is incorrect. Edited by author 15.11.2009 18:42 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. How to use information about sum of entire sequence? I've solved this problem for any sum of sequence, not only S+N. But algo is quite complicated. Is there any way to simplify algo using information about sum of sequence? probably if you subtract 1 from every element, you get simpler problem. My program works like that: int sum = 0; int sum1 = 0; int i = 0; for( int j = 0; j < s; j++) { cin >> temp; sum1 += temp; if( sum1 > n + j + 1) { cout << "NO" << endl; return 0; } if( temp < 3) { sum = 0; i = j + 1; } else { sum += temp; if( sum > n + j - i + 1) { cout << "NO" << endl; return 0; } } } cout << "YES" << endl; ==========> WA in #12 V_V My first AC submission on test s = 5 n = 2 1 3 0 3 0 answers YES, but correct is NO (sorry for bad english) "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" var sum,s,n,i,j,k:longint; a:array[1..100]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. Think about simpler solution -> without array - just O(n) !! I got AC without any array! ) 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. use for i:=1 to s do for j:=i to s do begin .... end; {1<=i<=j<=s} Aidin_n7@hotmail.com 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 (3+0)<=(3-2+1)+3 Yes, just 373K and it's AC. Check that it's a sequence. very nice problem !!! jus a bit of thinking reqd Nice - i agree. For others only 10 strings - AC - 0.015 Nice - i agree. For others only 10 strings - AC - 0.015 ... int main() { ... scanf("%d%d",&s,&n); sum=s+n; for (i=0;i<s;i++) { scanf("%d",&t); sum-=t; ... } while (sum); ... return 0; } I have TLE4 ... My algo is O(n)... I have TLE in "while (sum);"... I think in test4 sum of Ai not equal S+N... sorry for my bad english :) 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! I've solved this problem by using algorithm: my pseudo code: ...... for (i=0; i<S; i++) { for (j=i; j<S and j<i+3; j++) if (sum_from_I_to_J(i,j) > j-i+1 + N) then begin out("NO"); return(0); end; for (j=i+S-10; j<S and j>=i; j++) if (sum_from_I_to_J(i,j) > j-i+1 + N) then begin out("NO"); return(0); end; } out("YES"); .... It was a test solution, I did't thought that I'll got AC. I don't understand, why it works? Thanks. ps sorry for my bad english. #include <iostream.h> int main() { long S,N,Sum; bool X; int A[30000]; cin>>S;cin>>N; Sum=0;X=1; for(long i=1;i<=S;i++)cin>>A[i]; for(long i=S;i>=1;i--) { Sum+=A[i]; if(Sum>S-i+1+N)X=0; } if(X==0) cout<<"NO"; else cout<<"YES"; return 0; } 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 According to problem rules: Is it right that for all 1 <= i <= j <= S the following inequality holds: Ai + Ai-1 + ... + Aj <= (j – i + 1) + N? I do not understand the last line. if j>=i then why Ai + Ai-1 + ... + Aj Does it mean Ai+Ai-1+Ai-2+...+A1+Aj or Aj+Aj-1+Aj-2+Aj-3+...+Ai+1+Ai if yes then waht should i do when i=j Ai+Aj or olny Ai It should be Ai + Ai+1 + ... + Aj. > It should be Ai + Ai+1 + ... + Aj. Right. It is missprint here. Help me please!!! ------------------------------------- var s,n,sum,i,j,k,a:longint; procedure solve(i:integer); var j:integer; begin for j:=i to s do readln; end; begin readln(s,n); k:=0; for i:=1 to s do begin read(a); inc(k); if a<>0 then sum:=sum+a else begin if sum>k+n then begin solve(i); write('No'); halt; end else if sum<k then begin sum:=0; k:=0; end end; end; if sum>k+n then write('No') else write('Yes'); end. ---------------------------------- Thank you!!! Just think when it is most likely the inequality won't be true ! When You realize it You'll get AC ! |
|