QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#270967 | #2925. Parking Lot | PetroTarnavskyi# | AC ✓ | 493ms | 109152kb | C++20 | 1.8kb | 2023-12-01 19:01:17 | 2023-12-01 19:01:17 |
Judging History
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'