program de;
    var
    a,b:array[-1400..1400] of integer;
    a1,b1:array[1..2800] of integer;
    i,j,n,max_a,max_b:integer;
    ch:char;
procedure diog;
begin
        if ch='s' then
            begin
             b[i-j]:=0;
             inc(a[i-j]);
             if a[i-j]>max_a then max_a:=a[i-j];
            end
         else
           begin
             a[i-j]:=0;
             inc(b[i-j]);
             if b[i-j]>max_b then max_b:=b[i-j];
            end;
end;
procedure diogobrat;
begin
        if ch='s' then
            begin
             b1[i+j]:=0;
             inc(a1[i+j]);
             if a1[i+j]>max_a then max_a:=a1[i+j];
            end
         else
           begin
             a1[i+j]:=0;
             inc(b1[i+j]);
             if b1[i+j]>max_b then max_b:=b1[i+j];
            end;
end;
procedure vivod;
begin
   if max_a=max_b then
      begin
        writeln('?');
        writeln(max_a);
      end
   else
   if max_a<max_b then
      begin
        writeln('S');
        writeln(max_b);
      end
   else
      begin
        writeln('s');
        writeln(max_a);
      end;
end;
begin
{   assign(input,'c:\test.txt');
   reset(input);                   }
   readln(n);
   for i:=1 to n do
   begin
     for j:=1 to n do
      begin
        read(ch);
        diog;
        diogobrat;
      end;
      readln;
   end;
   vivod;
end.

Maybe you are using expressions like (n-j) for j=0...n-i-1 and 0-indexing when checking diagonals.  So,  (n-j)  results in WA #8. Correct expression is (n-1-j)

Really dont know what the mistake???


int main() {
    char src[1405][1405];

    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        for(int z = 0; z < n; z++) {
            cin >> src[i][z];
        }
    }

    int s = 0, S = 0;

    for(int i = 0; i < n; i++) {
        int tmps = 0, tmpS = 0;
        for(int z = 0; z < n; z++) {
            if(src[i][z] == 's') {
                tmps++;
                s = max(s, tmps);
                tmpS = 0;
            } else {
                tmpS++;
                S = max(S, tmpS);
                tmps = 0;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        int tmps = 0, tmpS = 0;
        for(int z = 0; z < n; z++) {
            if(src[z][i] == 's') {
                tmps++;
                s = max(s, tmps);
                tmpS = 0;
            } else {
                tmpS++;
                S = max(S, tmpS);
                tmps = 0;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        int tmps = 0, tmpS = 0;
        for(int z = 0; z <= i; z++) {
            if(src[i - z][z] == 's') {
                tmps++;
                s = max(s, tmps);
                tmpS = 0;
            } else {
                tmpS++;
                S = max(S, tmpS);
                tmps = 0;
            }
        }
    }

    for(int i = 0; i < n; i++) {
        int tmps = 0, tmpS = 0;
        for(int z = i; z < n; z++) {
            if(src[z][z - i] == 's') {
                tmps++;
                s = max(s, tmps);
                tmpS = 0;
            } else {
                tmpS++;
                S = max(S, tmpS);
                tmps = 0;
            }
        }
    }

    if(s > S) {
        cout << "s\n" << s;
    } else if(s < S) {
        cout << "S\n" << S;
    } else {
        cout << "?\n" << s;
    }
}

I don't see any dynamic programming in this problem...

can someone please explain the problem, specially the part "(parallel to the north-south or east-west directions or at the angle 45° to them)" and the first sample input-output.

4
SSsS
sssS
SSsS
Ssss
output
s
4

I used only ~2MB in C#, but want to know how to improve it.
Thx.

[code deleted]

sorry.stupid mistake.AC

Edited by author 20.07.2010 18:09

Make a macro for "for"

#define F(i,n) for(int i = 0; i < n; ++i)

macros for start/process/stop of each line
 #define START int c0 = 0, ...
 #define P(x) if(x == 's'){ ...
 #define STOP mc0 = max(mc0, c0); ...

vertical/horizontal lines are simple:
  F(i,n){ START; F(j,n) P(s[i][j]); STOP; }
  F(i,n){ START; F(j,n) P(s[j][i]); STOP; }

The simplest diagonal is
  F(i,n)  { START; F(j,i+1) P(s[  i-j ][  j ]); STOP; }

with a macro for symmetry
#define I(ind) n-1-(ind)

the other lines simply invert some of coordinates:
  F(i,n)  { START; F(j,i+1) P(s[I(i-j)][  j ]); STOP; }
  F(i,n-1){ START; F(j,i+1) P(s[  i-j ][I(j)]); STOP; }
  F(i,n-1){ START; F(j,i+1) P(s[I(i-j)][I(j)]); STOP; }

If you use Java pay attention to size of arrays, that you used.
I used 2 arrays for saving current line and prev line of input(every has o(n) elements), and 2 arrays for saving result of calculating in prev Line, and for saving result of calculation in current line (every has o(n) elements).

Edited by author 21.02.2010 15:56

program Ural1287;

var
  map:array[0..1401,0..1401]of boolean;
  ans,i,j,n,k:longint;
  c:char;

function max(a,b:longint):longint;

begin
  if a>b then exit(a) else exit(b);
end;

procedure dm(i,j:longint);

begin
  if ans=k then if map[i,j]xor(c='S') then c:='?';
  if ans<k then
  begin
    ans:=k;
    if map[i,j] then c:='S'
    else c:='s';
  end;
  k:=1;
end;

begin
  readln(n);
  for i:=1 to n do
    begin
      for j:=1 to n do
        begin
          read(c);
          map[i,j]:=c='S';
        end;
      readln;
    end;
  c:=' ';
  for i:=1 to n do
    begin
      k:=1;
      for j:=2 to n do
        begin
          if map[i,j]=map[i,j-1] then inc(k)
          else dm(i,j-1);
        end;
      dm(i,n);
    end;
  for i:=1 to n do
    begin
      k:=1;
      for j:=2 to n do
        begin
          if map[j,i]=map[j-1,i] then inc(k)
          else dm(j-1,i);
        end;
      dm(n,i);
    end;
  for i:=1 to n do
    begin
      k:=1;
      for j:=i+1 to n do
        begin
          if map[j-i+1,j]=map[j-i,j-1] then inc(k)
          else dm(j-i,j-1);
        end;
      dm(j-i+1,n);
      k:=1;
      for j:=i+1 to n do
        begin
          if map[j,j-i+1]=map[j-i,j-1] then inc(k)
          else dm(j-1,j-i);
        end;
      dm(n,j-i+1);
    end;
  for i:=1 to n do
    begin
      k:=1;
      for j:=2 to i do
        begin
          if map[i-j+1,j]=map[i-j+2,j-1] then inc(k)
          else dm(i-j+2,j-1);
        end;
      dm(i,1);
      k:=1;
      for j:=2 to i do
        begin
          if map[j,i-j+1]=map[j-1,i-j+2] then inc(k)
          else dm(j-1,i-j+2);
        end;
      dm(1,i);
    end;
  writeln(c);
  writeln(ans);
end.

Wa#11 Who can help me???

I keep getting WA on testcase 4, but I'm sure my program is correct. Can someone give me this test or send me AC program or just tell me what is the trick in this testcase?

1
s

I'm curious how some people coped with so less memory, probably they've read char by char and not knowing the whole map but I don't know how to do it :( I got TL and ML consequently :(

I think that following two input routines are the same:
#1, gets AC
-------------------------
ReadLn(N);
For I := 1 To N Do
 begin
  For J := 1 To N Do
   begin
    Read(Ch);
    <work>
   end;
  ReadLn;
 end;
----------------------
#2, gets WA on test 4
----------------------
Read(N);
Read(Ch);
For I := 1 To N Do
 For J := 1 To N Do
  begin
   While Not((Ch = 's')Or(Ch = 'S')) Do Read(Ch);
   <work>
   Read(Ch);
  end;
-----------------------------
Where am I mistake?