QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#501505 | #5153. Delft Distance | naichakafei | WA | 10ms | 23828kb | C++20 | 1.9kb | 2024-08-02 19:46:44 | 2024-08-02 19:46:45 |
Judging History
answer
/*
/\_/\
(= ._.)
/ > \>
*/
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cassert>
#define int long long
#define double long double
using namespace std;
const int N = 1010, M = 1e6 + 10, MOD = 1e9 + 7;
pair<int, int> a[N];
string s[N];
bool st[N];
double f[N][N][3];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = '#' + s[i];
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j][0] = (double)(i * 10 + j * 10);
f[i][j][1] = (double)(i * 10 - 5 + j * 10);
f[i][j][2] = (double)(i * 10 + j * 10 - 5);
}
}
double pi = 3.1415926535897;
double d = 2.5 * pi, t = 5;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j][1] = min(f[i][j][1], f[i - 1][j][0] + t);
f[i][j][2] = min(f[i][j][2], f[i][j - 1][0] + t);
if (s[i][j] == 'O') {
f[i][j][1] = min(f[i][j][1], f[i - 1][j - 1][0] + t + d);
f[i][j][2] = min(f[i][j][2], f[i - 1][j - 1][0] + t + d);
}
if (s[i][j] == 'O' && s[i + 1][j] == 'O') {
f[i + 1][j][1] = min(f[i + 1][j][1], f[i - 1][j - 1][0] + t + 2 * d);
f[i + 1][j][2] = min(f[i + 1][j][2], f[i - 1][j - 1][0] + t * 3 + d);
}
if (s[i][j] == 'O' && s[i][j + 1] == 'O') {
f[i][j + 1][1] = min(f[i][j + 1][1], f[i - 1][j - 1][0] + t * 3 + d);
f[i][j + 1][2] = min(f[i][j + 1][2], f[i - 1][j - 1][0] + t + 2 * d);
}
f[i][j][0] = min(f[i][j][0], min(f[i][j][1], f[i][j][2]) + t);
}
}
printf("%.10Lf", f[n][m][0]);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int TT = 1;
//cin >> TT;
while (TT--) {
solve();
}
return 0;
}
/*
/\_/\
(= ._.)
/ > \>
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3924kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.4159265359
result:
ok found '71.4159265', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
1 4 XOOX
output:
45.7079632679
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
1 1 X
output:
20.0000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
1 1 O
output:
17.8539816340
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 3 XOO
output:
35.7079632679
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
1 5 OXOOO
output:
55.7079632679
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
142.8318530718
result:
ok found '142.8318531', expected '142.8318531', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4136kb
input:
1 2 XX
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
10 1 X X X O O O X O O X
output:
105.7079632679
result:
ok found '105.7079633', expected '105.7079633', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
18 6 OOOOOO OOOOOO XOOOOO OOOOXO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOX OOOOOO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
output:
214.2477796077
result:
ok found '214.2477796', expected '214.2477796', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
40 9 OOOOXOXXX XOXXXOXXO OXOXXXXXO OXOXXXOXX XXXXOXOXX XXOOXOXXX XOOXOXXXX XOXXOOXOX OXXOOOOXX XXOOOXXOO OXOOXOXXX OOOOOXOOO OXXXXXXXO OOOOOOOXX OOOXXXOOX OXOXXOOOO OOOOXOXOO OXOXOOOXO OXXOOXXXO OXOOXOOXO XXXOXOXOO XXOOOXOOX OOXXOOXOO XOOXXXXOX OXXXXOOOO OXOOOOXOX XXOXXXOOO OOXOOOXXX OXOOOOXOO OXOOO...
output:
453.5176877776
result:
ok found '453.5176878', expected '453.5176878', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 6216kb
input:
41 50 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...
output:
873.5176877776
result:
ok found '873.5176878', expected '873.5176878', error '0.0000000'
Test #13:
score: 0
Accepted
time: 3ms
memory: 21020kb
input:
329 527 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
8560.0000000000
result:
ok found '8560.0000000', expected '8560.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 0ms
memory: 6480kb
input:
49 297 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
3451.4159265359
result:
ok found '3451.4159265', expected '3451.4159265', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 20636kb
input:
357 83 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
4342.0575041173
result:
ok found '4342.0575041', expected '4342.0575041', error '0.0000000'
Test #16:
score: -100
Wrong Answer
time: 10ms
memory: 23828kb
input:
417 615 XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...
output:
9749.1591146372
result:
wrong answer 1st numbers differ - expected: '9736.2830044', found: '9749.1591146', error = '0.0013225'