QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270967#2925. Parking LotPetroTarnavskyi#AC ✓493ms109152kbC++201.8kb2023-12-01 19:01:172023-12-01 19:01:17

Judging History

This is the latest submission verdict.

  • [2023-12-01 19:01:17]
  • Judged
  • Verdict: AC
  • Time: 493ms
  • Memory: 109152kb
  • [2023-12-01 19:01:17]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;

const db EPS = 1e-9;
const db LINF = 1e18;

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	int n, m;
	cin >> n >> m;
	vector<string> vec(n);
	for (string& row : vec)
		cin >> row;
	vector<VI> pref(n, VI(m + 1));
	FOR(i, 0, n)
		FOR(j, 0, m)
			pref[i][j + 1] = pref[i][j] + (vec[i][j] == '#');
	int vertices = (n + 1) * (m + 1);
	vector<vector<db>> g(vertices, vector<db>(vertices, LINF));
	FOR(i1, 0, n + 1) FOR(j1, 0, m + 1) FOR(i2, 0, n + 1) FOR(j2, 0, m + 1)
	{
		bool ok = true;
		FOR(r, min(i1, i2), max(i1, i2))
		{
			if (j1 == j2)
				break;
			db c1 = j1 + (db)(r - i1) / (i2 - i1) * (j2 - j1);
			db c2 = j1 + (db)(r + 1 - i1) / (i2 - i1) * (j2 - j1);
			if (c1 > c2)
				swap(c1, c2);
			int k1 = clamp((int)(c1 + EPS), 0, m - 1);
			int k2 = clamp((int)(c2 - EPS), 0, m - 1);
			ok &= pref[r][k2 + 1] - pref[r][k1] == 0;
		}
		if (ok)
			g[(m + 1) * i1 + j1][(m + 1) * i2 + j2] = sqrt((i2 - i1) * (i2 - i1) + (j2 - j1) * (j2 - j1));
	}
	vector<db> d(vertices, LINF);
	VI used(vertices);
	d[0] = 0;
	FOR(i, 0, vertices)
	{
		int v = -1;
		FOR(j, 0, vertices)
			if (!used[j] && (v == -1 || d[j] < d[v]))
				v = j;
		used[v] = 1;
		FOR(j, 0, vertices)
			if (!used[j])
				d[j] = min(d[j], d[v] + g[v][j]);
	}
	cout << d[vertices - 1] << "\n";
	cerr << (db)clock() / CLOCKS_PER_SEC << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

input:

1 1
.

output:

1.414213562373095

result:

ok found '1.4142136', expected '1.4142136', error '0.0000000'

Test #2:

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

input:

1 1
#

output:

2.000000000000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #3:

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

input:

1 3
.#.

output:

3.414213562373095

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #4:

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

input:

1 3
##.

output:

3.414213562373095

result:

ok found '3.4142136', expected '3.4142136', error '0.0000000'

Test #5:

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

input:

2 3
.#.
.#.

output:

3.828427124746190

result:

ok found '3.8284271', expected '3.8284271', error '0.0000000'

Test #6:

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

input:

2 6
#..#.#
#.#..#

output:

6.472135954999580

result:

ok found '6.4721360', expected '6.4721360', error '0.0000000'

Test #7:

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

input:

6 5
.####
#...#
#.##.
#.###
##...
####.

output:

8.226772762414360

result:

ok found '8.2267728', expected '8.2267728', error '0.0000000'

Test #8:

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

input:

12 10
##########
##########
###....###
##########
#..####..#
###....###
#######.##
...#######
###....###
#######..#
###....###
##########

output:

18.944271909999159

result:

ok found '18.9442719', expected '18.9442719', error '0.0000000'

Test #9:

score: 0
Accepted
time: 463ms
memory: 109152kb

input:

50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..........................................

output:

70.710678118654747

result:

ok found '70.7106781', expected '70.7106781', error '0.0000000'

Test #10:

score: 0
Accepted
time: 15ms
memory: 10244kb

input:

13 47
...............................................
...............................................
...............................................
...............................................
...............................................
...............................................
.........

output:

48.764741360946438

result:

ok found '48.7647414', expected '48.7647414', error '0.0000000'

Test #11:

score: 0
Accepted
time: 469ms
memory: 109012kb

input:

50 50
##################################################
##################################################
##################################################
##################################################
##################################################
#######################################...

output:

100.000000000000000

result:

ok found '100.0000000', expected '100.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 33ms
memory: 10208kb

input:

47 13
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
#############
...

output:

60.000000000000000

result:

ok found '60.0000000', expected '60.0000000', error '0.0000000'

Test #13:

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

input:

49 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

49.010203019371382

result:

ok found '49.0102030', expected '49.0102030', error '0.0000000'

Test #14:

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

input:

49 1
.
.
#
#
#
.
.
.
.
.
#
#
#
#
#
#
#
#
#
#
.
.
.
.
#
.
.
.
.
#
#
#
.
#
#
.
.
#
#
#
#
#
.
#
#
.
.
.
.

output:

49.099019513592784

result:

ok found '49.0990195', expected '49.0990195', error '0.0000000'

Test #15:

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

input:

3 45
.............................................
.............................................
.............................................

output:

45.099889135118723

result:

ok found '45.0998891', expected '45.0998891', error '0.0000000'

Test #16:

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

input:

3 45
###..####.##.#.#.##..#.#############...##.###
##.###..#.##.#.##.#.#...#.......#...##..###.#
###...##..##........#..###.#...#..#.#.....#..

output:

45.406155302958050

result:

ok found '45.4061553', expected '45.4061553', error '0.0000000'

Test #17:

score: 0
Accepted
time: 469ms
memory: 108988kb

input:

50 50
..................................................
........#.........................................
..................................................
..................................................
..................................................
..........................................

output:

70.710678118654747

result:

ok found '70.7106781', expected '70.7106781', error '0.0000000'

Test #18:

score: 0
Accepted
time: 15ms
memory: 10224kb

input:

13 47
......................................#........
...............................................
...........#.....#.............................
...............................................
...............................................
...............................................
.........

output:

48.764741360946438

result:

ok found '48.7647414', expected '48.7647414', error '0.0000000'

Test #19:

score: 0
Accepted
time: 217ms
memory: 61712kb

input:

40 46
..............................................
......................#................#......
...........................#..................
............#.................................
..............................................
..............................................
...............

output:

60.959002616512684

result:

ok found '60.9590026', expected '60.9590026', error '0.0000000'

Test #20:

score: 0
Accepted
time: 469ms
memory: 108976kb

input:

50 50
........................#.........................
.......#.......#....#.........#.............#.....
...............#..................................
.........#...........#................#..#........
....#........#............................#....##.
....#.....#....................#.#........

output:

70.981171949535491

result:

ok found '70.9811719', expected '70.9811719', error '0.0000000'

Test #21:

score: 0
Accepted
time: 29ms
memory: 10280kb

input:

47 13
..........#..
.............
.............
..........#..
....#....#...
...##........
...#......#..
.............
.............
.............
.............
.............
...........#.
.............
........#....
.............
.............
........#....
........#..#.
.............
.............
...

output:

48.772481298873393

result:

ok found '48.7724813', expected '48.7724813', error '0.0000000'

Test #22:

score: 0
Accepted
time: 213ms
memory: 61700kb

input:

40 46
.......#...........#.#.......#................
.#..............................#........#....
...........................#..............#...
..............#...............................
.....................................#.......#
.#..........................#...........#.....
.......#.......

output:

61.131208710736194

result:

ok found '61.1312087', expected '61.1312087', error '0.0000000'

Test #23:

score: 0
Accepted
time: 457ms
memory: 108932kb

input:

50 50
.#...###.#..#.#.....#.#..###..#.#..#.....###.##.#.
####..###..#...##..######.##..#####..##.###..##.##
#####..#..###..##..#.#..#.##...#.#####.##..#####.#
....##....#.#####.#.##.##....#.###.#...#.#.##.##.#
##.....#.##.########..##..#....#.##..#.##.##...#..
###.#..##.##.#####.##..##.#.#.#.#.#..##...

output:

74.464129641099157

result:

ok found '74.4641296', expected '74.4641296', error '0.0000000'

Test #24:

score: 0
Accepted
time: 289ms
memory: 73020kb

input:

47 43
#.#...#.#...##.#.##.##.#.#....#.####.#..#..
.####....#..#..#..#.#...####...#.#.......##
.#.#####.#..#..#..#####.#####.#.#.###..##.#
.###.#####.#....######...#.#.#.#..##.###...
.#.###.......#..#####..#######..#..#....#.#
#..####..#.##.#..#..##.#.#.###.####.###.#..
.#.##.#####.#.##.##..##.#.##.....

output:

67.730078556521580

result:

ok found '67.7300786', expected '67.7300786', error '0.0000000'

Test #25:

score: 0
Accepted
time: 295ms
memory: 79448kb

input:

44 48
##....###...#.#..##....###..##.##.....###.###...
#..##..#..#........###.###....##.##..##...#.###.
.#....###...#.......#.###..##..##...#.####.#....
.#.#.###...#.#..#..###..##....###..####....#.#..
...#.#.#...##..#..###.###.#.#..#...#.###..##.#..
##.#.###...####.#..#..#####.##..#.##.##.........
...

output:

69.059701689189864

result:

ok found '69.0597017', expected '69.0597017', error '0.0000000'

Test #26:

score: 0
Accepted
time: 457ms
memory: 109092kb

input:

50 50
..#.####..#.##########..#######.####.#.#.#########
....#####.##..#########.#######.##.##..##.####..#.
##.#####.##.#.###.##..#.#.#####..#######.###.#####
.##..######..#.########.#..######..######.######.#
##.#################.#####.##..##.########.#######
###.#.#..##.#########.#.###.####.##.###...

output:

81.587028629833314

result:

ok found '81.5870286', expected '81.5870286', error '0.0000000'

Test #27:

score: 0
Accepted
time: 453ms
memory: 109004kb

input:

50 50
#####.#######.##..#...########..#####.###..###.#.#
###.#####.#.##....#....#.###.#####.###.###.##.##.#
..#.######..#..##..#..######.####.#.#########..##.
#####..####.###.##.########.#.###########.###.###.
###.#######.###....##########..###.##.#.###.#..###
.##..##.##.###.##.#########.#.###.#####...

output:

80.710134255450976

result:

ok found '80.7101343', expected '80.7101343', error '0.0000000'

Test #28:

score: 0
Accepted
time: 458ms
memory: 109132kb

input:

50 50
#..#####..######..##.#####.###########.##.###.###.
#.######.##.###.##.####.###.#####.###.#.##...#####
#########.##..##.####...#.##########.#####.#######
########...#..#..#####.##.#####.##.###.#..#######.
.##############.######..###.#..#####.######.####.#
##.##.#.###.##.#.#####.#..##.###.##.###...

output:

81.335092727628600

result:

ok found '81.3350927', expected '81.3350927', error '0.0000000'

Test #29:

score: 0
Accepted
time: 473ms
memory: 108980kb

input:

50 50
##.########.#####################.#######..######.
###.#####.##.###.########...####..##########.#..##
##.#.##.##...##.###########.#####.####.##.######.#
#..#####..###.#.##.######.##########.###.###.#####
###.####..########.#.######.###.####.########..###
######.##.#######.#######.#..######...#...

output:

80.722980040229038

result:

ok found '80.7229800', expected '80.7229800', error '0.0000000'

Test #30:

score: 0
Accepted
time: 458ms
memory: 108932kb

input:

50 50
#########.##########.##.############.#######.#####
#########################.#######.########.#######
..###########.#######.#####.#######..#######.##.##
##########.##################.###################.
############.#########.################..#.#######
#########.##########.######.##.########...

output:

86.733966568137061

result:

ok found '86.7339666', expected '86.7339666', error '0.0000000'

Test #31:

score: 0
Accepted
time: 464ms
memory: 108920kb

input:

50 50
########..#############.###################..#####
#######.############.############.#####.##########
###########.#########################..#####.##.##
#####.###############.##################.#####.###
################..############..#########.########
#############################.######.##...

output:

86.941172205932881

result:

ok found '86.9411722', expected '86.9411722', error '0.0000000'

Test #32:

score: 0
Accepted
time: 453ms
memory: 108992kb

input:

50 50
#####..#.##.######.#########..#######.##..########
###################...####################.######.
.####.######.###########.#######################.#
################.##########.##..################.#
######.#.#################.#########.#########.#.#
##########..######.#############.######...

output:

86.400116032714872

result:

ok found '86.4001160', expected '86.4001160', error '0.0000000'

Test #33:

score: 0
Accepted
time: 462ms
memory: 109124kb

input:

50 50
.###############.#########.##.###.#########.######
#####.###..##############.###########.#.#########.
################.#####.##############.#######.####
#######..###.####################.#.#####.###..###
#####.#.####.#####.####.#.######################.#
#######.################.##.#####.##.##...

output:

86.400116032714872

result:

ok found '86.4001160', expected '86.4001160', error '0.0000000'

Test #34:

score: 0
Accepted
time: 470ms
memory: 109004kb

input:

50 50
....##############################################
###.....##########################################
#######.....######################################
###########.....##################################
###############....###############################
###################.###################...

output:

74.291187073645499

result:

ok found '74.2911871', expected '74.2911871', error '0.0000000'

Test #35:

score: 0
Accepted
time: 470ms
memory: 108920kb

input:

50 50
.#################################################
.#################################################
..################################################
#.################################################
#.################################################
#..####################################...

output:

74.860444267458867

result:

ok found '74.8604443', expected '74.8604443', error '0.0000000'

Test #36:

score: 0
Accepted
time: 457ms
memory: 109008kb

input:

50 50
.#################################################
..################################################
#..###############################################
##..##############################################
###..#############################################
####.##################################...

output:

72.680036434438801

result:

ok found '72.6800364', expected '72.6800364', error '0.0000000'

Test #37:

score: 0
Accepted
time: 455ms
memory: 109000kb

input:

50 50
.#################################################
..################################################
#.################################################
#..###############################################
##..##############################################
###.###################################...

output:

71.901173734596025

result:

ok found '71.9011737', expected '71.9011737', error '0.0000000'

Test #38:

score: 0
Accepted
time: 467ms
memory: 108992kb

input:

50 50
.#################################################
.#################################################
.#################################################
.#################################################
.#################################################
.######################################...

output:

80.073847135070583

result:

ok found '80.0738471', expected '80.0738471', error '0.0000000'

Test #39:

score: 0
Accepted
time: 463ms
memory: 109000kb

input:

50 50
.#################################################
..################################################
#.################################################
#..###############################################
##.###############################################
##..###################################...

output:

76.602990072988224

result:

ok found '76.6029901', expected '76.6029901', error '0.0000000'

Test #40:

score: 0
Accepted
time: 464ms
memory: 108996kb

input:

50 50
...###############################################
##....############################################
#####...##########################################
########...#######################################
##########....####################################
#############...#######################...

output:

76.784316009703922

result:

ok found '76.7843160', expected '76.7843160', error '0.0000000'

Test #41:

score: 0
Accepted
time: 454ms
memory: 109004kb

input:

50 50
.#################################################
#.################################################
##.###############################################
###.##############################################
####.#############################################
#####.#################################...

output:

75.996520402741753

result:

ok found '75.9965204', expected '75.9965204', error '0.0000000'

Test #42:

score: 0
Accepted
time: 493ms
memory: 108960kb

input:

50 50
.#################################################
#.################################################
##.###############################################
###.##############################################
####.#############################################
#####.#################################...

output:

72.574307361665477

result:

ok found '72.5743074', expected '72.5743074', error '0.0000000'

Test #43:

score: 0
Accepted
time: 455ms
memory: 108992kb

input:

50 50
.#################################################
#.################################################
##.###############################################
###.##############################################
####.#############################################
#####.#################################...

output:

76.409090965389104

result:

ok found '76.4090910', expected '76.4090910', error '0.0000000'

Test #44:

score: 0
Accepted
time: 454ms
memory: 108916kb

input:

50 50
.#################################################
#.################################################
##.###############################################
###.##############################################
####.#############################################
#####.#################################...

output:

73.436493747078618

result:

ok found '73.4364937', expected '73.4364937', error '0.0000000'

Test #45:

score: 0
Accepted
time: 464ms
memory: 109012kb

input:

50 50
.#################################################
#.################################################
##.###############################################
###.##############################################
####.#############################################
#####.#################################...

output:

73.768178500419414

result:

ok found '73.7681785', expected '73.7681785', error '0.0000000'

Test #46:

score: 0
Accepted
time: 465ms
memory: 109012kb

input:

50 50
.#################################################
#.################################################
#..###############################################
##..##############################################
###..#############################################
####..#################################...

output:

70.829147264146619

result:

ok found '70.8291473', expected '70.8291473', error '0.0000000'

Test #47:

score: 0
Accepted
time: 460ms
memory: 109076kb

input:

50 50
.#################################################
#..###############################################
##..##############################################
###..#############################################
####..############################################
#####..################################...

output:

70.733748503300492

result:

ok found '70.7337485', expected '70.7337485', error '0.0000000'

Test #48:

score: 0
Accepted
time: 469ms
memory: 109088kb

input:

50 50
.#################################################
#.################################################
#..###############################################
##..##############################################
###..#############################################
####..#################################...

output:

71.441202117241799

result:

ok found '71.4412021', expected '71.4412021', error '0.0000000'

Test #49:

score: 0
Accepted
time: 458ms
memory: 109008kb

input:

50 50
........................##########################
#######################........................###
###############################################.##
###############################################.##
###############################################.##
#######################################...

output:

95.249234123745518

result:

ok found '95.2492341', expected '95.2492341', error '0.0000000'

Test #50:

score: 0
Accepted
time: 458ms
memory: 109132kb

input:

50 50
.............#####################################
#############.............########################
##########################.............###########
#######################################.##########
#######################################.##########
#######################################...

output:

87.399548782098181

result:

ok found '87.3995488', expected '87.3995488', error '0.0000000'

Test #51:

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

input:

4 4
..#.
.#.#
###.
.#..

output:

5.886349517372675

result:

ok found '5.8863495', expected '5.8863495', error '0.0000000'

Test #52:

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

input:

2 2
##
##

output:

4.000000000000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'