QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140920#5153. Delft Distanceemailam#WA 1ms5896kbC++201.6kb2023-08-16 23:25:582023-08-16 23:26:02

Judging History

你现在查看的是最新测评结果

  • [2023-08-16 23:26:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5896kb
  • [2023-08-16 23:25:58]
  • 提交

answer

#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cin.tie(nullptr), cout.tie(nullptr);

#include <bits/stdc++.h>

#define ll long long
#define double long double
using namespace std;

const int N = 705;

int n, m;
char arr[N][N];
double dp[N][N][4];
// 1 -> right to me
// 2 -> down

vector<vector<double>> fromTo[3] = {
        {{1, 5, 0}, {2, 5,                 0}},
        {{0, 5, 1}, {2, 10 * acos(-1) / 4, 1}},
        {{0, 5, 2}, {1, 10 * acos(-1) / 4, 2}},
};

double solve(int x, int y, int edge) {
    if (x == n && y == m && !edge) {
        return 0;
    }
    if (x > n || y > m)return 1e9;
    double &ret = dp[x][y][edge];
    if (ret != -1)return ret;
    ret = 1e9;
    if (arr[x][y] == 'X') {
        ret = min(solve(x + 1, y, 0), solve(x, y + 1, 0)) + 10;
    } else {
        for (auto i: fromTo[edge]) {
            ret = min(ret, solve(x + (i[2] == 2), y + (i[2] == 1), i[0]) + i[1]);
        }
    }
    return ret;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int k = 0; k < 4; ++k) {
                dp[i][j][k] = -1;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i <= m; ++i) {
        arr[n + 1][i] = 'X';
    }
    for (int i = 0; i <= n; ++i) {
        arr[i][m + 1] = 'X';
    }
    cout << setprecision(8) << solve(0, 0, 0);
}

signed main() {
    io
    int t;
    t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3732kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.415927

result:

ok found '71.4159270', expected '71.4159265', error '0.0000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

1 4
XOOX

output:

45.707963

result:

ok found '45.7079630', expected '45.7079633', error '0.0000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

1 1
X

output:

20

result:

ok found '20.0000000', expected '20.0000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

1 1
O

output:

17.853982

result:

ok found '17.8539820', expected '17.8539816', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

1 3
XOO

output:

35.707963

result:

ok found '35.7079630', expected '35.7079633', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5896kb

input:

1 5
OXOOO

output:

55.707963

result:

ok found '55.7079630', expected '55.7079633', error '0.0000000'

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 5680kb

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

147.12389

result:

wrong answer 1st numbers differ - expected: '142.8318531', found: '147.1238900', error = '0.0300496'