QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#501505#5153. Delft DistancenaichakafeiWA 10ms23828kbC++201.9kb2024-08-02 19:46:442024-08-02 19:46:45

Judging History

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

  • [2024-08-02 19:46:45]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:23828kb
  • [2024-08-02 19:46:44]
  • 提交

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'