-1

Edited by author 03.01.2008 14:22

My ansewer -1

use standart input and output stream...

Use scanf instead of cin
Input file is very big >10MB

but better use Pascal:)
I don't optimize input at all. It works about 1.3 sec

After simple optimization 0.328 sec

Edited by author 26.01.2007 16:15

Try to use "gets()" instead "scanf()" and "cin". You can solve it with 2 strings (length = 2*m + 2). I've get AC at 0.156 sec. And some solution are faster.

1
a-b

program ex;

const
  maxn=2000;
  maxm=50;
  zero=1e-15;

var
  g: Array[0..maxn, 1..maxm] of extended;
  cost: Array[1..maxn] of longint;
  from: Array[1..maxn] of longint;
  n, m: longint;
  ans: longint;
  num: Array[1..maxm] of longint;
  tot: longint;
  kk: Array[1..maxn] of longint;

procedure init;
var
  i, j: longint;
begin
  read(n, m);
  for i:=1 to n do
    for j:=1 to m do
      read(g[i, j]);
  for i:=1 to n do begin
    read(cost[i]);
    from[i]:=i;
  end;
end;

procedure qsort(l, r: longint);
var
  i, j: longint;
  x, y: longint;
  t: longint;
begin
  i:=l;
  j:=r;
  x:=cost[(l+r) shr 1];
  y:=from[(l+r) shr 1];
  while i<=j do begin
    while (cost[i]<x)or(cost[i]=x)and(from[i]<y) do inc(i);
    while (cost[j]>x)or(cost[j]=x)and(from[j]>y) do dec(j);
    if i<=j then begin
      g[0]:=g[i];
      g[i]:=g[j];
      g[j]:=g[0];
      t:=cost[i];
      cost[i]:=cost[j];
      cost[j]:=t;
      t:=from[i];
      from[i]:=from[j];
      from[j]:=t;
      inc(i);
      dec(j);
    end;
  end;
  if j>l then qsort(l, j);
  if i<r then qsort(i, t);
end;

function can(x: longint): boolean;
var
  i, j: longint;
  len1, len2: extended;
  sum: extended;
  co: extended;
  tt: extended;
  temp: Array[1..maxn] of extended;
begin
  for i:=1 to tot do begin
    sum:=0;
    len1:=0;
    len2:=0;
    for j:=1 to m do begin
      sum:=sum+g[x, j]*g[i, j];
      len1:=len1+g[x, j]*g[x, j];
      len2:=len2+g[kk[i], j]*g[kk[i], j];
    end;
    len1:=sqrt(len1);
    len2:=sqrt(len2);
    if abs(len1)<=zero then
      exit(false);
    co:=sum/len1/len2;
    tt:=len1*co;
    for j:=1 to m do
      temp[j]:=g[kk[i], j]*tt/len2;
    for j:=1 to m do
      g[x, j]:=g[x, j]-temp[j];
  end;
  for j:=1 to m do
    if abs(g[x, j])>zero then
      exit(true);
  exit(false);
end;

procedure solve;
var
  i: longint;
begin
  qsort(1, n);
  tot:=1;
  num[1]:=from[1];
  ans:=ans+cost[1];
  kk[1]:=1;
  for i:=2 to n do
    if can(i) then begin
      inc(tot);
      kk[tot]:=i;
      num[tot]:=from[i];
      ans:=ans+cost[i];
      if tot=m then
        exit;
    end;
end;

procedure print;
var
  i, j: longint;
  t: longint;
begin
  if tot<m then
    writeln(0)
  else begin
    writeln(ans);
    for i:=1 to m do
      for j:=i+1 to m do
        if num[i]>num[j] then begin
          t:=num[i];
          num[i]:=num[j];
          num[j]:=t;
        end;
    for i:=1 to m do
      writeln(num[i]);
  end;
end;

begin
  init;
  solve;
  print;
end.

can you tell me what the mistake is. coz im also getting WA in test#1 itself

YEAAAAAH, I got AC!!!

I used DP O(n^2)
var
  st : ansistring;
  f : array [0..1010,0..1010] of boolean;
  i,j,cx,cy,max : longint;
begin
  readln(st); max:=0;
  for i:=1 to length(st) do
  for j:=1 to i do f[i,j]:=true;
  for i:=1 to length(st)-1 do
  for j:=1 to length(st)-i do
  if st[j] = st[i+j] then f[j,i+j]:=f[j+1,i+j-1]
                     else f[j,i+j]:=false;

  max:=-1;
  for i:=1 to length(st) do
  for j:=0 to length(st)-i do
  if (f[i,i+j]) and (j>max) then
  begin
    cx:=i;
    cy:=i+j;
    max:=j;
  end;

  for i:=cx to cy do write(st[i]);
  writeln;
end.

>

>

Can you just explain in simple terms the method you've used.

Edited by author 01.12.2007 02:29

Example test is not test #1.

use seekeof for numbers
StrToFloat(IntToStr(a[j])) is not needed
use extended

when you submit your code you can use option
"reply to this email"

maybe you use Visual Studio 6.0 and it's stupid compiler
for (int i=0;i<k;i++) // there you define i
{
tmp*=n;
n--;
} // end of area where i is visible
for (i=1;i<=k;i++)
^^^^^^^^^^ i is undefined there
{
d*=i;
}

in c++ standart you can do such cicles
for (int i = 0; i < 4; i++) .....
for (int i = 0; i < 4; i++) .....

but stupid VS 6.0 compiler think that it is wrong
anyway you can do as this:

int i;
for (i = 0; i < 4; i++) ...
for (i = 0; i < 4; i++) ...

Edited by author 18.11.2007 13:27