QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140917#5153. Delft Distanceemailam#WA 1ms5844kbC++201.6kb2023-08-16 23:23:262023-08-16 23:23:28

Judging History

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

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

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

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(7) << 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: 0ms
memory: 5792kb

input:

3 5
XOOXO
OXOXO
XXXXO

output:

71.41593

result:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

1 4
XOOX

output:

45.70796

result:

ok found '45.7079600', expected '45.7079633', error '0.0000001'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3664kb

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: 5844kb

input:

1 1
O

output:

17.85398

result:

ok found '17.8539800', expected '17.8539816', error '0.0000001'

Test #5:

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

input:

1 3
XOO

output:

35.70796

result:

ok found '35.7079600', expected '35.7079633', error '0.0000001'

Test #6:

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

input:

1 5
OXOOO

output:

55.70796

result:

ok found '55.7079600', expected '55.7079633', error '0.0000001'

Test #7:

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

input:

6 10
XXXXXOOOOX
XXOOOOOOOO
XXXOXOOXOX
OXOXOXXOOX
OOXXOXXXXO
OXOXXOOXOO

output:

147.1239

result:

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