QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234854 | #5537. Storing Eggs | dmmm# | WA | 161ms | 3772kb | C++14 | 2.5kb | 2023-11-02 00:00:03 | 2023-11-02 00:00:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;
const int maxN = 1e2 + 6.9;
int n, k;
char a[4][maxN];
bool ok(int i, int j, int j2, int d2) {
if (j == 3 && j2 == 3) return i * i >= d2 && 4 >= d2;
if (j < 3 && j2 < 3) return i * i + (j - j2) * (j - j2) >= d2;
if (j < 3) swap(j, j2);
int dj = min(j2, 3 - j2);
return i * i + dj * dj >= d2 && 4 >= d2;
}
bool check(int d2) {
vector<vector<int>> dp(n + 1, vector<int>(4, -INF));
for (int i = 1; i <= n; i++)
for (int j = 0; j < 4; j++) {
if (j < 3 && a[j][i] == '#') continue;
if (j == 3 && (a[0][i] == '#' || a[2][i] == '#' || d2 > 4)) continue;
int num = j == 3 ? 2 : 1;
dp[i][j] = num;
// for (int i2 = i - 1; i2 >= 1; i2--)
// for (int j2 = 0; j2 < 4; j2++) {
// if (d2 == 5 && i >= 3 && i - i2 <= 2) {
// if (i2 == i - 1) continue;
// if (!ok(i - i2, j, j2, d2)) continue;
// int good = 0;
// for (int j3 = 0; j3 < 3; j3++)
// if (ok(1, j, j3, d2) && ok(i - 1 - i2, j2, j3, d2) && a[j3][i - 1] == '.') good = 1;
// dp[i][j] = max(dp[i][j], dp[i2][j2] + num + good);
// }
// else if (ok(i - i2, j, j2, d2)) {
// if (dp[i2][j2] + num > dp[i][j])
// dp[i][j] = dp[i2][j2] + num;
// }
// }
for (int i2 = i - 1; i2 >= 1; i2--)
for (int j2 = 0; j2 < 4; j2++) {
int num2 = j2 == 3 ? 2 : 1;
if (ok(i - i2, j, j2, d2) && dp[i2][j2] > 0) {
dp[i][j] = max(dp[i][j], num2 + num);
}
for (int i3 = i2 - 1; i3 >= 1; i3--)
for (int j3 = 0; j3 < 4; j3++) {
if (ok(i - i2, j, j2, d2) && ok(i - i3, j, j3, d2) && ok(i2 - i3, j2, j3, d2) && dp[i2][j2] > 0)
dp[i][j] = max(dp[i][j], num2 + num + dp[i3][j3]);
}
}
if (dp[i][j] >= k) return 1;
}
// for (int j = 0; j < 4; j++) {
// for (int i = 1; i <= n; i++) cout << dp[i][j] << ' ';
// cout << '\n';
// }
return 0;
}
int bin(int l, int r) {
while (l < r) {
int mid = (r - l) / 2 + l + 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
int num = 0;
for (int i = 0; i < 3; i++) {
string s;
cin >> s;
for (int j = 1; j <= n; j++) {
a[i][j] = s[j - 1];
if (s[j - 1] == '.') num++;
}
}
if (num < k) return cout << -1, 0;
double ans = 1;
// cout << check(21);
int res = bin(2, INF);
if (check(res)) ans = sqrt(res);
cout << fixed << setprecision(7) << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3672kb
input:
5 2 #.... ..... ....#
output:
4.4721360
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 6 ##.## ##### .....
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
3 4 ..# ... ...
output:
1.4142136
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
1 2 . . .
output:
2.0000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 65ms
memory: 3616kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.0202000
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 73ms
memory: 3600kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.0407993
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 144ms
memory: 3760kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.0000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 159ms
memory: 3676kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.4142136
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #10:
score: 0
Accepted
time: 160ms
memory: 3764kb
input:
100 151 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 158ms
memory: 3600kb
input:
100 200 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 161ms
memory: 3760kb
input:
100 201 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 33ms
memory: 3592kb
input:
60 130 ............................................................ ............................................................ ............................................................
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 98ms
memory: 3760kb
input:
100 100 .................................................................................................... #################################################################################################### .............................................................................................
output:
2.0000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 43ms
memory: 3768kb
input:
100 51 #################################################################################################### .................................................................................................... ###########################################################################################...
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
1 2 # # #
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 41ms
memory: 3592kb
input:
99 50 ################################################################################################### ................................................................................................... ##############################################################################################...
output:
2.0000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 59ms
memory: 3664kb
input:
100 47 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
output:
2.8284271
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #19:
score: 0
Accepted
time: 56ms
memory: 3596kb
input:
100 43 .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
output:
2.8284271
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #20:
score: 0
Accepted
time: 62ms
memory: 3592kb
input:
99 2 #........#............#.#.#...................................#................##..............#... ............................##...#......#...##.............#.........#..#...#............#...#..... #...............................................#..............#.....#.........#.........#........
output:
98.0051019
result:
ok found '98.0051019', expected '98.0051020', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
90 2 #############..######.###.##.#########.###.###########.####.############################## #...##########.#.#################.############.########################.################# ###################.###.##.####.#######..##.########.#############################.#######
output:
81.0061726
result:
ok found '81.0061726', expected '81.0061730', error '0.0000000'
Test #22:
score: 0
Accepted
time: 56ms
memory: 3596kb
input:
95 3 #.#..............#.............#.......#..##.....#.#............#....#..................##..... .....#.#........#...#...........#......................#...#.....#.........#.....#...........#. #.......#.#....#.......#.......#.......#..#.#.#.#....#.#...#..#......#........#..........#....#
output:
47.0106371
result:
ok found '47.0106371', expected '47.0106370', error '0.0000000'
Test #23:
score: 0
Accepted
time: 4ms
memory: 3596kb
input:
92 3 #########################.###########################.####################################.# #######.##############.#.#################.#########.########.#############################. ###.##.####.###.####.#####.########.#########.########.##.#######.##########################
output:
42.0000000
result:
ok found '42.0000000', expected '42.0000000', error '0.0000000'
Test #24:
score: 0
Accepted
time: 54ms
memory: 3764kb
input:
93 4 ##..#.......................#.....#.#.#..............#.....#........#.....................#.. ......#...................#..##...................#...............###.....#....#..........#.# #......#.........#....#.................#......#...#......##..........#.........#.#..#.#..#.#
output:
30.0665928
result:
ok found '30.0665928', expected '30.0665930', error '0.0000000'
Test #25:
score: 0
Accepted
time: 9ms
memory: 3632kb
input:
92 4 ###.###############.######.##.#########################.######.###.#####.################### #.##..#####################.###########################.########..###############.#######... #######################.###.############.##..####.#################.#.#..####.##############
output:
28.0178515
result:
ok found '28.0178515', expected '28.0178510', error '0.0000000'
Test #26:
score: 0
Accepted
time: 74ms
memory: 3624kb
input:
94 5 #........#....#.................................................#.....................#....... #................#...............#..##..................#........#.......#...#................ ##..................................................##................#.......#...............
output:
23.0217289
result:
ok found '23.0217289', expected '23.0217290', error '0.0000000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
1 2 # . .
output:
1.0000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #28:
score: 0
Accepted
time: 8ms
memory: 3676kb
input:
94 5 ##..#.######.##.########.#####.#####.############..##.##############################..######## #######.########.##########.#..################.####.#.###...######..##.###################### ######.############.######.#####################.################.##.##############.##########
output:
18.0277564
result:
ok found '18.0277564', expected '18.0277560', error '0.0000000'
Test #29:
score: 0
Accepted
time: 62ms
memory: 3764kb
input:
90 6 #.................#....................#................#.#.........###................... ....................................#........#...................#...##...##....#.....#... #.#...........#...#........#..#....#.#....................#.........#.....................
output:
17.1172428
result:
ok found '17.1172428', expected '17.1172430', error '0.0000000'
Test #30:
score: 0
Accepted
time: 10ms
memory: 3760kb
input:
100 6 ##########.##.##################.###########.###########.##.######################.####.##.######### ##########...#########.#.########.#################.#.###########.#.##########.#.##.################ ##############.#####..#######..##################.#######################.########.#########...
output:
16.0312195
result:
ok found '16.0312195', expected '16.0312200', error '0.0000000'
Test #31:
score: 0
Accepted
time: 68ms
memory: 3712kb
input:
92 7 #.#....#..#...#.......#.........................................#.......#...#.............#. ...............#......#............#...#.........................#.....#..............#..... #..#......#...............#.................#....#............................#.............
output:
15.1327460
result:
ok found '15.1327460', expected '15.1327460', error '0.0000000'
Test #32:
score: 0
Accepted
time: 11ms
memory: 3696kb
input:
92 7 ##.###########..######.###############.#.##.#################.##.#############.######.###.## #############.###############.##..#####################.######.#..#########.###.############ .###.########.###################.########.###################..#######...#########.#####.##
output:
14.0356688
result:
ok found '14.0356688', expected '14.0356690', error '0.0000000'
Test #33:
score: 0
Accepted
time: 69ms
memory: 3768kb
input:
91 8 #..................#..#..............#......................#.......#..........#...#..#.... #....#.#.....#..#......#.....#.................#..#...........................#.........#.. #.......#......#..........#............#.....#...................#..............#.....#....
output:
12.1655251
result:
ok found '12.1655251', expected '12.1655250', error '0.0000000'
Test #34:
score: 0
Accepted
time: 8ms
memory: 3628kb
input:
93 8 ############.###########.#######################.############.##.###.######################.# ############.####.###########.#######.####.##########.#######.####.###################.####.. #####.#######.###########.#####.#############.#.##################.##########################
output:
8.0622577
result:
ok found '8.0622577', expected '8.0622580', error '0.0000000'
Test #35:
score: 0
Accepted
time: 130ms
memory: 3600kb
input:
100 109 ..#.....#..............#....................#..#.......#.............#................#.#........... #............##.........#..........#.#....#...............#...#.......#................#...........# .....#..#......#................................................................#............
output:
1.4142136
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #36:
score: 0
Accepted
time: 91ms
memory: 3772kb
input:
97 13 ..##...#..........#.........##....##......#............#..........###........#.....#.........#... ##..#....#.............#....#...#.##............#........#.#.#.....................#.......#..#.. ........#..#....##.........#.#....#.....#.......#.#...................#......#.......#......##...
output:
8.0622577
result:
ok found '8.0622577', expected '8.0622580', error '0.0000000'
Test #37:
score: 0
Accepted
time: 92ms
memory: 3592kb
input:
100 50 ....#......#..................#.......#..#.....#........#.........#......#....#............##....... #.....##........#.#...........##..#....##....#.#.........##....#.##...........#..................... ......##........#...#....#...#...#............#.......##.#..........##......##....##..#...#...
output:
2.2360680
result:
ok found '2.2360680', expected '2.2360680', error '0.0000000'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3380kb
input:
1 3 # . .
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #39:
score: 0
Accepted
time: 94ms
memory: 3768kb
input:
92 107 ..#........#...#...#.....#....#........#...#.......#.........#..#.........#...##.......##.#. ..##.......#..#....##.#..##.#.##........#............#..#.......#..##..............#....#... #...#.....#..........#........#.....##.#.................#....##...........#............#...
output:
1.4142136
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #40:
score: -100
Wrong Answer
time: 101ms
memory: 3592kb
input:
95 125 ...##.......#..#.#.............#..##...#..................#......#...##..#.....##....#.......#. .........#.....#.#....#....#..##.....#...#...#......#...........##..#........#.#...#.#........# .#..#....................##.........#...#...........#...........#...#...#..........##.....#.##.
output:
1.4142136
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '1.4142136', error = '0.4142136'