I use Dynamic Programming..and i made several tests myself, my code could calculate the right answer = =...sorry for my poor English

It's neccesary to use dances with diamonds to get AC in java without ML =))

Recoursive DP and DFS gets ML12, but iterative DP and BFS with queue based on arrays gets AC.

I think that the same (Rec DP+DFS) solution in C++ can pass all tests without troubles..

    Can you give me a hint about TEST#27?I have been checked my program for 2 days.And I can't find what's wrong with my program.I'm crazy!
  Here is my program:
  program puzzle;
const
  maxn=410;
var
  d,f:array [0..maxn,0..maxn] of longint;
  b,e,s,a:array [0..maxn] of longint;
  t,vis:array [0..maxn] of boolean;
  ch:array [0..maxn] of char;
  i,j,p,k,l,m,n:longint;
procedure init;
  begin
    read(n,m);
    for i:=1 to m do read(a[i]);readln;
    for i:=1 to n do
      begin
        repeat
         read(ch[i]);
        until ch[i] in ['?','X','.'];
      end;
    readln;
  end;
procedure solve;
  begin
    for i:=1 to n do
      begin
        s[i]:=s[i-1];
        if ch[i]='X' then inc(s[i]);
      end;
    fillchar(d,sizeof(d),-$3f);
    d[n+1,m+1]:=0;
    k:=n;
    for i:=n downto 1 do
      begin
        for j:=m+1 downto 1 do
          begin
            d[i,j]:=d[i+1,j];
            if (j=m+1) or (i+a[j]-1>n) or (ch[i]='.') then continue;
            if i+a[j]+1>n then l:=n+1 else l:=i+a[j]+1;
            if (i+a[j]-1<=k) and (d[l,j+1]>=0) and (d[l,j+1]+s[i+a[j]-1]-s[i-1]>d[i,j])
              then d[i,j]:=d[l,j+1]+s[i+a[j]-1]-s[i-1];
          end;
        if ch[i]='.' then k:=i-1;
      end;
    if d[1,1]<>s[n] then begin writeln('Impossible');exit; end;
    fillchar(f,sizeof(f),-$3f);
    f[0,0]:=0;
    k:=1;
    for i:=1 to n do
      begin
        for j:=0 to m do
          begin
            f[i,j]:=f[i-1,j];
            if (j=0) or (i<a[j]) or (ch[i]='.') then continue;
            if i-a[j]-1<1 then l:=0 else l:=i-a[j]-1;
            if (i-a[j]+1>=k) and (f[l,j-1]>=0) and (f[l,j-1]+s[i]-s[i-a[j]]>f[i,j])
              then f[i,j]:=f[l,j-1]+s[i]-s[i-a[j]];
          end;
        if ch[i]='.' then k:=i+1;
      end;
    fillchar(vis,sizeof(vis),false);
    fillchar(t,sizeof(t),false);
    fillchar(b,sizeof(b),255);
    p:=0;
    for i:=1 to n do
      begin
        if ch[i]='.' then begin p:=i;continue; end;
        for j:=1 to m do
          begin
            if i-a[j]+1<=p then continue;
            if i+2<=n then k:=d[i+2,j+1] else begin if j<m then continue;k:=0; end;
            if i-a[j]-1>0 then inc(k,f[i-a[j]-1,j-1]) else begin if j>1 then continue; end;
            if s[i]-s[i-a[j]]+k=s[n]
              then begin
                     for l:=i-a[j]+1 to i do t[l]:=true;
                     if b[j]=-1
                       then begin
                              b[j]:=i-a[j]+1;e[j]:=i;
                              continue;
                            end;
                     if e[j]<i-a[j]+1
                       then begin
                              b[j]:=i-a[j]+1;e[j]:=i;
                              vis[j]:=true;
                            end;
                     if vis[j] then continue;
                     b[j]:=i-a[j]+1;
                   end;
          end;
      end;
    for i:=1 to n do if not t[i] and (ch[i]='?') then ch[i]:='.';
    for i:=1 to m do
      begin
        if vis[i] then continue;
        for j:=b[i] to e[i] do ch[j]:='X';
      end;
    for i:=1 to n do write(ch[i]);writeln;
  end;
begin
  assign(input,'puzzle.in');reset(input);
  assign(output,'puzzle.out');rewrite(output);
  init;
  solve;
  close(input);close(output);
end.

At last.Sorry for my poor English.

    I got WA on it about 20 times.I'm crazy now!
    Please help me.
    Thank you!

deffinitely
->
definitely
(used twice in statement)

Also I suggest the following change:
The first line contains the length of the row L and the number of groups of consecutive cells that must be painted (1 ≤ L ≤ 400). The second line contains K integers (0 ≤ K ≤ L), which are the lengths of these groups.
->
The first line contains the length of the row L (1 ≤ L ≤ 400) and the number of groups of consecutive cells that must be painted K (0 ≤ K ≤ L). The second line contains K integers, which are the lengths of these groups.

I can't imagine how its possible. Test 1 == Sample Test 1, I think.

Here is my code (I delete it when I find the bug):

[code deleted]

Oh, I am too stupid... Don't read this!!!!!!!!

Edited by author 17.08.2007 13:33

Does anybody know what test #27 is? I made two different programs and both were stoped here. Now I am really confused...
Thanks in andvance.

In the description of input, "The second line contains K integers". If K = 0, the second should be empty line.
But in Sample input #2
9 0
??????.X?

There is not so-called second line.
So I read data like following. and got WA at 3.
----------------
Readln(N, M);
if M > 0 then
begin
    for i := 1 to M do
        Read(L[i]);
    Readln;
end;
for i := 1 to N do
    Read(T[i]);
----------------

Then I suppose sample input #2 is wrong, there must be an empty line in second line when K = 0.
I change code like following. and got WA at 20.
----------------
Readln(N, M);
for i := 1 to M do
    Read(L[i]);
Readln;
for i := 1 to N do
    Read(T[i]);
----------------

It implys there is some invalid char in input file.
So I change code like following. and got AC.

Readln(N, M);
for i := 1 to M do
    Read(L[i]);
for i := 1 to N do
    repeat
        Read(T[i]);
    until T[i] in ['X', '.', '?'];

So there must be something wrong in testcase.