fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cmath>
  4. #define min(x,y) ((x<y) ? (x) : (y))
  5. using namespace std;
  6. int x,y;
  7. float dp[1001][1001];
  8. bool d[1001][1001];
  9. float solve(int x,int y) {
  10.     if (dp[x][y]!= -1.0)
  11.         return dp[x][y];
  12.     if (x == 0 && y == 0)
  13.         return (dp[x][y] = 0.0);
  14.     if (x == 0 )
  15.         return (dp[x][y] = y*100);
  16.     if (y == 0)
  17.         return (dp[x][y] = x*100);
  18.     float ret;
  19.     float r1,r2,r3;
  20.     r1 = 100.0 + solve(x-1,y);
  21.     r2 = 100.0 + solve(x,y-1);
  22.     ret = min(r1,r2);
  23.     if (d[x][y]) {
  24.         r3 = solve(x-1,y-1);
  25.         r3 = r3 + 141.42;
  26.         ret = min(ret,r3);
  27.     }
  28.     dp[x][y] = ret;
  29.     return ret;
  30. }
  31. int main() {
  32.     cin >> x >> y;
  33.     int k;
  34.     int d1,d2;
  35.     cin >> k;
  36.     memset(dp,-1.0,sizeof dp);
  37.     memset(d,false,sizeof d);
  38.     for (int i=0;i<k;i++) {
  39.         cin >> d1 >> d2;
  40.         d[d1][d2]=true;
  41.     }
  42.     float dist = solve(x,y);
  43.     int ans = dist;
  44.     if (dist - ans > 0.5) {
  45.         ans++;
  46.     }
  47.     cout << ans << endl;
  48. }
  49.  
Success #stdin #stdout 0s 7992KB
comments (?)
stdin
copy 
3 2
3
1 1
3 2
1 2
stdout
copy 
-2147483648
https://ideone.com/6C2WjR
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!