Submission #19220


Source Code Expand

Copy
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)

#define EPS (1e-9)
#define EQ(a,b) (abs(a-b)<EPS)

#define INF 100000.0

const int MAXN=512;
char C[MAXN][MAXN];
double U[MAXN][MAXN];
const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
int W,H;

void solve(int t,int x,int y)
{
    rep(4)
    {
        const int xx = x+dx[i];
        const int yy = y+dy[i];

        if(xx<0||yy<0||xx>=W||yy>=H) continue;
        if(C[yy][xx]=='#'||C[yy][xx]=='s') continue;

        double g = (C[yy][xx]=='g'?INF:(C[yy][xx]-'0')*pow(0.99,t));
        double s = min(g,U[y][x]);

        if(EQ(s,U[yy][xx])||s<U[yy][xx]) continue;
        U[yy][xx]=s;

        if(C[yy][xx]!='g') solve(t+1,xx,yy);
    }
}

int main()
{
    cin>>H>>W; rep(H) cin>>C[i];

    int sx,sy,gx,gy;

    REP(y,H) REP(x,W)
    {
        if( C[y][x] == 's' ){ sx=x; sy=y; }
        if( C[y][x] == 'g' ){ gx=x; gy=y; }
    }

    U[sy][sx]=INF;
    solve(1,sx,sy);

    printf("%0.9f\n",U[gy][gx]);

    return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User mitsuchie
Language C++ (G++ 4.6.4)
Score 0
Code Size 1202 Byte
Status WA
Exec Time 5030 ms
Memory 3364 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 15
WA × 18
TLE × 30
RE × 1
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 22 ms 824 KB
00_mini_02.txt AC 20 ms 788 KB
00_mini_03.txt AC 22 ms 760 KB
00_mini_04.txt AC 20 ms 784 KB
00_mini_05.txt WA 21 ms 800 KB
00_sample_01.txt AC 22 ms 736 KB
00_sample_02.txt AC 20 ms 764 KB
01_rnd_01.txt TLE 5029 ms 2172 KB
01_rnd_02.txt TLE 5029 ms 2692 KB
01_rnd_03.txt AC 3066 ms 1272 KB
01_rnd_04.txt WA 4378 ms 1792 KB
01_rnd_05.txt WA 918 ms 1300 KB
01_rnd_06.txt WA 207 ms 1148 KB
01_rnd_07.txt WA 2812 ms 2776 KB
01_rnd_08.txt TLE 5029 ms 3056 KB
01_rnd_09.txt TLE 5030 ms 2940 KB
01_rnd_10.txt TLE 5030 ms 3068 KB
01_rnd_11.txt TLE 5029 ms 2180 KB
01_rnd_12.txt TLE 5030 ms 1908 KB
01_rnd_13.txt WA 442 ms 1148 KB
01_rnd_14.txt TLE 5030 ms 2556 KB
01_rnd_15.txt TLE 5030 ms 1992 KB
01_rnd_16.txt AC 1884 ms 1656 KB
01_rnd_17.txt WA 1321 ms 2164 KB
01_rnd_18.txt WA 21 ms 788 KB
01_rnd_19.txt WA 23 ms 916 KB
01_rnd_20.txt WA 23 ms 1072 KB
02_maxrnd_01.txt TLE 5030 ms 2932 KB
02_maxrnd_02.txt TLE 5030 ms 3348 KB
02_maxrnd_03.txt TLE 5030 ms 3324 KB
02_maxrnd_04.txt TLE 5030 ms 3332 KB
02_maxrnd_05.txt RE 0 ms 3320 KB
02_maxrnd_06.txt TLE 5030 ms 3252 KB
02_maxrnd_07.txt TLE 5030 ms 3324 KB
02_maxrnd_08.txt TLE 5029 ms 3324 KB
02_maxrnd_09.txt TLE 5030 ms 3328 KB
02_maxrnd_10.txt TLE 5030 ms 3364 KB
02_maxrnd_11.txt TLE 5030 ms 3320 KB
02_maxrnd_12.txt TLE 5030 ms 3324 KB
02_maxrnd_13.txt TLE 5030 ms 3320 KB
02_maxrnd_14.txt TLE 5030 ms 3324 KB
02_maxrnd_15.txt TLE 5030 ms 3324 KB
02_maxrnd_16.txt TLE 5030 ms 3332 KB
02_maxrnd_17.txt WA 1787 ms 3188 KB
02_maxrnd_18.txt WA 61 ms 1396 KB
02_maxrnd_19.txt WA 40 ms 1340 KB
03_hard_01.txt TLE 5030 ms 3332 KB
03_hard_02.txt TLE 5030 ms 3328 KB
03_hard_03.txt AC 33 ms 1392 KB
03_hard_04.txt AC 70 ms 3200 KB
03_hard_05.txt TLE 5029 ms 3308 KB
03_hard_06.txt TLE 5030 ms 3320 KB
03_hard_07.txt AC 34 ms 1404 KB
03_hard_08.txt AC 64 ms 3200 KB
04_open_01.txt TLE 5030 ms 3256 KB
04_open_02.txt TLE 5030 ms 3328 KB
05_minihard_01.txt WA 63 ms 920 KB
05_minihard_02.txt WA 63 ms 992 KB
05_minihard_03.txt AC 22 ms 892 KB
05_minihard_04.txt AC 23 ms 916 KB
05_minihard_05.txt AC 64 ms 912 KB
05_minihard_06.txt WA 59 ms 892 KB
05_minihard_07.txt WA 22 ms 900 KB
05_minihard_08.txt WA 23 ms 908 KB