My O(N^2) solution works for 0.187s
but 10000 * 10000 = 1e8, it means that O(N^2) solution should work only for 1
second (not less), but in this task there is 0.5 sec and O(N^2) solution gets AC

Take care in the cases of multiple lines. I was thinking it wasn't possible and it was giving me WA5. When I took care of it I got AC.

a a b a a
answer: 1

I had TLE on test 12 and realized that I used only simple recursion. Once I fixed it I got AC.

Edited by author 08.08.2015 14:46

If you have problems with test #31, you must know that in test #31 there are now words)) only delimiter characters!

Some of these are not mentioned in the problem statement

- The input can have other separators than spaces, eg:  'Re ad' is two words and so is 'Re*ad'
- There is no word with length 0, so there can be two separators, eg:  'Re**ad' is two words not three (if you have WA#6 check this)
- Inputs are of multiple lines, so you can use EOF to check for end of input.

Edited by author 09.04.2013 17:18

Edited by author 09.04.2013 17:18

Var     ch:Char;
        S:Array[-1..200000] of Longint;
        tmp:String;
        n,i,j,p,q,k,maxx:Longint;
Function max(x,y:Longint):Longint;
Begin
        If x>y then max:=x else max:=y;
End;

Begin
        tmp:='';
        s[0]:=0;
        While not eof do
         Begin
          Read(ch);
          If ((ch in ['a'..'z']) or (ch in ['A'..'Z'])) then tmp:=tmp+ch
          Else If length(tmp)>0 then
           Begin
            inc(n);
            p:=length(tmp);

            If (n<3) then s[n]:=p
            Else s[n]:=max(s[n-2],s[n-3])+p;

            If s[n]>maxx then maxx:=s[n];

            tmp:='';

           End;
         End;

        If n=0 then Writeln(length(tmp)) Else
        Writeln(maxx);
End.

Please help. Tks

No. No test have the same word twice by the condition of the problem. Following tests are not correct(It's fact I got AC)
1.abc f abc
2.a a a a a
....

sdfa__Sdfa___fdsa__sdfaasdfa__asdfadsf____sdfa___adsfadsfa_sdaf_sdf_df__dsf__adsf__sadf_Sdf-_as

answer 37

asd=asasd==aiii

answer  7

this is my program:
program Tresh;
const
    SIZE = 1000;
var
    a : array[1..SIZE] of Byte;
    max : array[1..SIZE] of Longint;
    n : Longint;
function MaxFrase (i, cur : Longint) : Longint;
var
    j, curmax, curn : Longint;
begin
    curmax := 0;
    if i+2 > n then begin
        MaxFrase := cur+a[i];
        Exit;
    end;
    if max[i] <> 0 then
        MaxFrase := max[i]
    else begin
        for j := i+2 to n do begin
            curn := MaxFrase(j, cur+a[i]);
            if curn > curmax then
                curmax := curn;
            end;
        max[i] := curmax;
        MaxFrase := curmax;
    end;
end;
var
    ch, chpred : Char;
    cur : Byte;
    i : Longint;
begin
    i := 1;
    FillChar(max, SizeOf(Longint)*SIZE, 0);
    while not Eof do begin
        Read(ch);
        if not (ch in ['a'..'z', 'A'..'Z']) then begin
            if cur <> 0 then begin
                a[i] := cur;
                Inc (i);
            end;
            cur := 0;
        end
        else begin
{            if ch <> chpred then}
            Inc (cur);
            chpred := ch
        end;
    end;
    if cur <> 0 then begin
        a[i] := cur;
        Inc (i);
        cur := 0;
    end;
    n := i-1;
    Writeln (MaxFrase(1, 0))
end.

What is a test 5?

Edited by author 06.07.2007 20:56

I didn't understand the question. What must our program to do??? Please answer to my question!!!!!!!1

I send same solution on Java and C++. Outcome was TLE#15 (I didn't use standart Java class and didn't realloc memory) and AC (with time 0.078).
Please, make double time limit for Java.

I advice you not to skip problems for your pleasure and scill.
So help me now in crack-problem. I have Wa2 because missunderstanding.
Example: S=aAbb cc bq hhd qss.
What  cost(S), where cost(S)is a  functional of optimization.
I think that:
1. We compress repeating letters to one sound because man onle hearing- S=ab c bd qs;
2. Form 3 possible subsequences
S1=ab bd =abbd=abd; cost(S1)=cost(abd)=3;
S2=ab qs=abqs;cost(S2)=cost(abqs)=4;
S3=c qs=cqs;cost(cqs)=3;
3. Take max result
 cost(S)=max(4,3,3)=4.
What wrong in my analysis?

Is it mumbling in this examples:
asd dree
middle

[AC CODE]

Edited by author 24.01.2006 19:33

[code deleted]

My program give right answers on all tests in this forum, but I have WA on test #2 :) Why ? :)

Edited by moderator 22.02.2006 22:12