QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140917 | #5153. Delft Distance | emailam# | WA | 1ms | 5844kb | C++20 | 1.6kb | 2023-08-16 23:23:26 | 2023-08-16 23:23:28 |
Judging History
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'