this program isn't AC (WA test#10) because of the
precision of the answer, but Pascal solution using the
same ideas is AC. If you can help me to deal with the
precision I would be very grateful to you. Still i'd
recommend you to write the problem in Pascal to avoid all
potential precision problems :

#include <iostream>
#include <cmath>

using namespace std;

struct cross{int x,y;};

int main()
{
    int m,n,k,i;
    cross a[100];
    cin >> m >> n >> k;

    if (!k) {cout << 100*(m+n); return 0;}

    for (i=0;i<k;i++) cin >> a[i].x >> a[i].y;

    bool f=false;
    cross t;

    while (!f)
    {
        f=true;
        for (i=0;i<k-1;i++)
            if (a[i].x>a[i+1].x)
                {t=a[i]; a[i]=a[i+1]; a[i+1]=t; f=false;}
            else if (a[i].x==a[i+1].x && a[i].y>a[i+1].y)
                {t=a[i]; a[i]=a[i+1]; a[i+1]=t; f=false;}
    }

    int d[100];
    int mx,j;

    d[k-1]=1;
    for (i=k-2;i>=0;i--)
    {
        d[i]=1; mx=0;
        for (j=k-1;j>i;j--)
            if (a[i].x<a[j].x && a[i].y<a[j].y && d[j]>mx) mx=d[j];
        d[i]+=mx;
    }

    double ans;

    ans=(double)100*((double)m+(double)n-(double)2*d[0]+sqrt((double)2)*(double)d[0]);
    cout << floor(ans+(double).5);

    return 0;
}

I have got AC for this problem but my solution is quite inefficient

http://acm.timus.ru/status.aspx?space=1&num=1119&author=82952

It takes me 0.156 seconds to compute the answer, but there are many ppl who got solution in 0.015 secs.If possible please email me one of the efficient solution (C++ one).my email address is pjas002@aucklanduni.ac.nz

Thanks

Could somebody help me, please?

Can U discribe my an idea of O(K^2) solving?
Thanks.

I used simple bfs and bitset - get AC!

http://acm.timus.ru/status.aspx?space=1&num=1119&author=66708

:)))

  I somehow get a compilation error if I use sqrt(2) from math.h. Any ideas? What do you compile with?

Help!
What's wrong with my program.
I get wrong answer in test2.
<
Program 1119;
Var
 amax,n,m,k,a,b,c,d:longint;
 shu:array[1..101]of record
                       x,y:longint;
                     end;
 an:array[1..101]of longint;

Function Qiu(u:longint):longint;
  var
   r:longint;
   max:longint;
  begin
    max:=1;
    for r:=1 to k do
      begin
        if (shu[u].x+1<=shu[r].x)and(shu[u].y+1<=shu[r].y)
          then begin
                 if an[r]=-1
                   then an[r]:=qiu(r);
                 if an[r]+1>max
                   then max:=an[r]+1;
               end;
      end;
    qiu:=max;
  end;

Begin
  readln(n,m);
  readln(k);
  for k:=1 to k do
    begin
      readln(shu[k].x,shu[k].y);
      an[k]:=-1;
    end;
  for a:=1 to k do
    begin
      for b:=1 to k do
        begin
          if ((shu[a].x<shu[b].x)or(shu[a].y<shu[b].y))
             or((shu[a].x=shu[b].x)and(shu[a].y<shu[b].y))
            then begin
                   c:=shu[a].x;d:=shu[a].y;
                   shu[a].x:=shu[b].x;shu[a].y:=shu[b].y;
                   shu[b].x:=c;shu[b].y:=d;
                 end;
        end;
    end;
  for a:=1 to k do
    an[a]:=Qiu(a);
  amax:=0;
  for a:=1 to k do
    begin
      if an[a]>amax
        then amax:=an[a];
    end;
  writeln((n+m-2*amax)*100+amax*100*sqrt(2):0:0);
End.
>

var m,n,k,i,j,max,s:longint;
    ma:array[0..200] of longint;
    a:array[0..200,1..2] of longint;
begin
  read(n,m,k);
  for i:=1 to k do read(a[i,1],a[i,2]);
  for i:=1 to k-1 do
    for j:=i+1 to k do
      if (a[i,1]>a[j,1])or((a[i,1]=a[j,1])and(a[i,2]>a[j,2]))
        then begin
               s:=a[i,1]; a[i,1]:=a[j,1]; a[j,1]:=s;
               s:=a[i,2]; a[i,2]:=a[j,2]; a[j,2]:=s
             end;
  for i:=k downto 1 do
    begin
      max:=0;
      for j:=i+1 to k do
        if (a[j,1]>a[i,1])and(a[j,2]>a[i,2])and(ma[j]>max) then
max:=ma[j];
      ma[i]:=max+1
    end;
  writeln(round((m+n-2*ma[1]+sqrt(2)*ma[1])*100))
end.

type
    list=array[1..2]of integer;
var
   a:array[0..100]of list;
   f1:list;
   f:array[0..100]of longint;
   i,j,k,m,n,max:longint;
begin
     fillchar(a,sizeof(a),0);
     readln(m,n);
     read(k);
     for i:=1 to k do
         read(a[i][1],a[i][2]);
     for i:=1 to k-1 do
         for j:=1 to k-i do
             if (a[j][1]>a[j+1][1]) or (a[j][2]>a[j+1][2]) then begin
                f1:=a[j];
                a[j]:=a[j+1];
                a[j+1]:=f1;
             end;
     f[0]:=0;
     for i:=1 to k do begin
         max:=0;
         for j:=0 to i do begin
             if (a[j][1]<a[i][1]) and (a[j][2]<a[i][2]) then if f[j]
+1>max then max:=f[j]+1;
         end;
         f[i]:=max;
     end;
     writeln((m+n-2*f[k]+sqrt(2)*f[k])*100:0:0);
end.

var m,n,k,i,j,max,s:integer;
    ma:array[1..100] of integer;
    a:array[1..100,1..2] of integer;
begin
  read(n,m,k);
  for i:=1 to k do read(a[i,1],a[i,2]);
  for i:=1 to k-1 do
    for j:=i+1 to k do
      if (a[i,1]>a[j,1])or((a[i,1]=a[j,1])and(a[i,2]>a[j,2]))
        then begin
               s:=a[i,1]; a[i,1]:=a[j,1]; a[j,1]:=s;
               s:=a[i,2]; a[i,2]:=a[j,2]; a[j,2]:=s
             end;
  for i:=k downto 1 do
    begin
      max:=0;
      for j:=i+1 to k do
        if (a[j,1]>a[i,1])and(a[j,2]>a[i,2])and(ma[j]>max) then
max:=ma[j];
      ma[i]:=max+1
    end;
  writeln(round((m+n-2*ma[1]+sqrt(2)*ma[1])*100))
end.

Hello everybody!

I have used an algorythm that i'm not sure there is or isn't
some subtle stupidity.
It is very simple:

You present the grid by the crossroads and for each crossroad
you find the max number of diagonals(MD) that you can go through from
the start point( crossroad 0,0 ) to the concerned crossroad (of
course
this will be the shortest way to it).
Then you can assume that the paths to all the crossroads which are on
north , east or north-east from this crossroad pass through this point
is shorter by  MD*( 200-100*sqrt(2) ) from the standart(with no
diagonals).
I stop explaining here, `cause my english is awlful, and i may confuse
you.

The code is short so i hope you understand it easily.
So if you can prove that it is wrong or can give me some
test with wa, I`ll be very grateful...

#include <iostream.h>
#include <math.h>

void printks();

class point{ //the crossroads
public:
    int x, y; //the coords
    int dgs;  // the number of diagonals that lead to that
crossroad,
                        //if you take the
shortest path
    point(){ dgs=0; }
} ks[110];

int k, n, m, cinx, ciny, tmpdgs, ind=0, indbr;
double long answer;

int main(){
    cin>>n>>m>>k;

    for (int br=0; br<k; br++){
        cin>>cinx>>ciny;

        tmpdgs=0;
        for ( indbr=0; indbr<ind; indbr++ )
        if ( (cinx-1)>=ks[indbr].x && (ciny-1)>=ks[indbr].y )
                if ( ks[indbr].dgs>tmpdgs ) tmpdgs= ks
[indbr].dgs;

        ks[ind].x=cinx;
        ks[ind].y=ciny;
        ks[ind].dgs=tmpdgs+1;
        ind++;
    }

    tmpdgs=0;
    for ( indbr=0; indbr<ind; indbr++ )
        if ( n>=ks[indbr].x && m>=ks[indbr].y && ks
[indbr].dgs>tmpdgs )
            tmpdgs=ks[indbr].dgs;

    answer= (n+m-2*tmpdgs)*100+sqrt(2)*100*tmpdgs ;

    if ( answer-floorl(answer)<=(long double)(0.49999999999) )
        cout<<(long)(floorl(answer))<<endl;
    else
        cout<<(long)(ceill(answer))<<endl;
    return 0;
}

It's seem a simple algo. But I can't find where my mistake's.
Here is my code. Thanks.

const maxk=1000;
var n,m,k:integer;
    a,x,y:array[1..maxk] of integer;

procedure inputdata;
var i:integer;
begin
   readln(n,m);
   readln(k);
   for i:=1 to k do readln(x[i],y[i]);
end;

procedure sort;
var i,j,tg:integer;
begin
   for i:=1 to n do
   for j:=i+1 to n do
   if (x[j]<x[i]) then
   begin
      tg:=x[i]; x[i]:=x[j]; x[j]:=tg;
      tg:=y[i]; y[i]:=y[j]; y[j]:=tg;
   end;
end;

procedure solve;
var i,j:integer;
begin
   for i:=1 to k do a[i]:=1;

   for i:=2 to k do
   for j:=1 to i-1 do
   if (x[j]<x[i]) and (y[j]<y[i]) then
   if a[i]<a[j]+1 then a[i]:=a[j]+1;
end;

procedure outputdata;
var i,max:integer;
    s:real;
begin
   max:=0;
   for i:=1 to k do if a[i]>max then max:=a[i];
   s:=(m+n-2*max)*100+sqrt(2)*100*max;
   writeln(s:0:0);
end;

begin
   inputdata;
   sort;
   solve;
   outputdata;
end.

Here is my source :

#include <stdio.h>
#include <math.h>

int m,n,k,primary=1,second=0;
char x[1100][130];
double min[2][1100];

void read_data()
 {
  int i,mod,_div,a,b;
  FILE *f=stdin;
  fscanf(f,"%d%d%d",&n,&m,&k);
  n++;m++;
  for(i=0;i<k;i++)
   {
    fscanf(f,"%d%d",&a,&b);
    mod=a & 7;
    _div=a >> 3;
    x[b][_div]=x[b][_div] | (1 << mod);
   }
 }

double minim(double a,double b)
 {
  return(a<=b?a:b);
 }

void solve()
 {
  int i,j,mod,_div;
  min[second][1]=0;
  for(i=2;i<=n;i++)min[second][i]=(i-1)*100;

  for(i=2;i<=m;i++)
   {
    min[primary][1]=min[second][1]+100;
    for(j=2;j<=n;j++)
     {
      min[primary][j]=minim(min[primary][j-1]+100,min[second][j]+100);
      mod=(j-1) & 7;_div=(j-1) >> 3;
      if(x[i-1][_div] & (1 << mod))
       min[primary][j]=minim(min[primary][j],min[second][j-1]+
                                                       (141.42135));
     }
    second=!second;primary=!primary;
   }
 }

void print()
 {
  printf("%ld",(long)ceil(min[second][n]));
 }

void main()
 {
  read_data();
  solve();
  print();
 }