# works on pypy

import sys

n, m = sys.stdin.readline().split()
n, m = int(n), int(m)
k = int(sys.stdin.readline())
can_diag = {tuple(map(int, sys.stdin.readline().split())):0 for _ in range(k)}
city_map = [[0]*(n+1) for _ in range(m+1)]
for i in range(n+1):
    city_map[0][i] = i*100
for i in range(m+1):
    city_map[i][0] = i*100
for i in range(1, m+1):
    for j in range(1, n+1):
        if (j, i) in can_diag:
            city_map[i][j] = 100*(2**0.5)+city_map[i-1][j-1]
        else:
            city_map[i][j] = 100+min(city_map[i][j-1], city_map[i-1][j])

print(round(city_map[-1][-1]))

I'm getting runtime error(access violation) on test case three. I don't know where I went wrong. Can anyone please help me?

Here is my code

using namespace std;
#include <iostream>
#include <cmath>
#include<bits/stdc++.h>
long long int n,m;
bool vi[1005][1005], di[1005][1005];
float dp[1005][1005];
#define inf 1e7
float shortest_path(int x, int y){//returns shortest path
    //base case
    if(x==n && y==m) return 0.0;
    if(x>n || y>m) return inf;
    //memorization
    if(vi[x][y]) return dp[x][y];
    //recursive relation
    float a,b,c = 20000.0;
    if(di[x][y]==1){
        a = sqrt(c) + shortest_path(x+1,y+1);//diagonal
        b = inf;
    }

    else
    {
        a = 100.0 + shortest_path(x+1,y);//left
        b = 100.0 + shortest_path(x,y+1);//up
    }

    float ans = min(a,b);
    dp[x][y] = ans;
    vi[x][y] = 1;
    return dp[x][y];
}

int main(){
    cin>>n>>m;
    int k;
    for (int i = 0; i < n*m; ++i)
    {
        for (int j = 0; j < n*m; ++j)
        {
            di[i][j] = 0;
            vi[i][j]=0;
            dp[i][j]=0;
        }
    }
    cin>>k;
    for (int i = 0; i < k; ++i)
    {
        int a,b;
        cin>>a>>b;
        di[a-1][b-1] = 1;
    }

    cout<<round(shortest_path(0,0))<<endl;

}

The problem test case is:
3 2
3
1 1
3 2
1 2
but is it right??
My observation finds:
3 2
3
1 1
3 2
2 1
plz help me???

I tried to solve this task by dp and bfs, but always have a TL on test 3.

I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales.

Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j])
where Diag[i][j] is either 100 * sqrt(2) or Infinity.
I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently?

I am using bfs to solve the problem but still getting TLE. Can anyone suugest the cause?

10 6
8
2 1
2 2
4 5
5 2
5 4
6 5
9 4
10 5

Ansver: 1366

#include<iostream>
#include <cmath>
#include <climits>
#include <deque>

using namespace std;

int v[1001][1001];
float table[1002][1002];

int metro(int n,int m,int k){
    deque<int> qi,qj;
    qi.push_back(1);
    qj.push_back(1);
    table[1][1] = 0;
    while(!qi.empty()){
        int i = qi.front(),j = qj.front();
        qi.pop_front();
        qj.pop_front();
        if(i <= n && table[i+1][j] > table[i][j]+100){
            qi.push_back(i+1);
            qj.push_back(j);
            table[i+1][j] = table[i][j]+100;
        }
        if(j <= m && table[i][j+1] > table[i][j]+100){
            qi.push_back(i);
            qj.push_back(j+1);
            table[i][j+1] = table[i][j]+100;
        }
        if(v[i][j] == 1){
            if(i <= n && j <= m && table[i+1][j+1] > table[i][j] + 141.4){
                qi.push_back(i+1);
                qj.push_back(j+1);
                table[i+1][j+1] = table[i][j]+(141.4);
            }
        }
    }
    return ceil(table[n+1][m+1]);
}

int main(){
    int n = 0,m = 0,k = 0;
    cin>>n>>m;
    for(int i = 0;i <= n+1;++i){
        for(int j = 0;j <= m+1;++j){
            v[i][j] = 0;
            table[i][j] = INT_MAX;
        }
    }
    cin>>k;
    for(int i = 0;i < k;++i){
        int x = 0,y = 0;
        cin>>x>>y;
        v[x][y] = 1;
    }
    cout<<metro(n,m,k)<<endl;
    return 0;
}

Edited by author 29.08.2016 16:40

Edited by author 29.08.2016 16:40

I am getting WA 5   Can anyone provide me the test case 5..  or hint to test case 5..

In a task it is told that a way of departure (1; 1) though, actually, the way of departure has to be (0; 0)

Messages should not contain correct solutions.

i use matrix of costs, each step set value of the cell as minimal of the

previous vertical cost + 100,
previous horizontal cost + 100,
previous diagonal cost + 100*sqrt(2)

the answer is Math.round(cost[M][N])

p.s.
cycle is organized from 1 to n, 1 to m inclusively


Edited by author 14.06.2015 17:09

this is my bad code
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
using namespace std;
struct poi
{
    int x,y;
};
vector<poi> g;
int n;
int ma=0;
vector<int> w;
bool compare(poi m,poi mm)
{
    if (m.x>mm.x)
    {
        return false;
    }
    else
    {
        return true;
    }
}
void dp(int t,int coun)
{
    if (coun>ma)
    {
        ma=coun;
    }
    for (int x=t+1; x<n; x++)
    {
        if ((g[x].x>g[t].x) and (g[x].y>g[t].y) and (coun+1)>w[x])
        {
            w[x]=coun+1;
            dp(x,coun+1);

        }
    }
}
int main()
{
    int a,b;
    poi t;
    scanf("%d%d%d",&a,&b,&n);
    w.resize(n);
    for (int x=0; x<n; x++)
    {
        scanf("%d%d",&t.x,&t.y);
        g.push_back(t);
        w[x]=0;
    }
    sort(g.begin(),g.end(),compare);
    for (int x=0; x<n; x++)
    {
        if (w[x]==0)
        {
            w[x]=1;
            dp(x,1);
        }
    }
    double ras=(a+b-2*ma)*100;
    ras+=ma*sqrt(20000);
    printf("%d", int(ras+0.5));
}




what is the test №13

 while (n>0)
      {
            b=a;
            b=b/pow(10,n-1) - rezult/pow(10,n-1);
            for (int i=1;i<10;i++)
            if ((b-i>=0)&(b-i-1<0))  rezult += (i)*pow(10,n-1);
            n--;
      }
/*
if delete :

b=b/pow(10,n-1) - rezult/pow(10,n-1);
            for (int i=1;i<10;i++)
            if ((b-i>=0)&(b-i-1<0))  rezult += (i)*pow(10,n-1);

- work! */

first the person goes to (2,2) from (1,1) +141 then (3,2) +100 so why not 241?

Note Accuracy

give me test,pleasee

Could I get the data of the test 3

who know this error please explain for me please. Give me test 10. Thank you!!!

Consider two test cases:
3 3
3
1 2
2 3
3 1
and
3 3
3
1 3
2 1
3 2
Although they are symmetric and the answers must be equal, my AC programs (5180921 or 5180891) output different answers for them.