QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #713844 | #5537. Storing Eggs | MeatInTheMiddle | WA | 105ms | 8824kb | C++17 | 4.9kb | 2024-11-05 20:41:45 | 2024-11-05 20:41:46 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;
const double inf = 50000;
double d[101][1 << 3][101][1 << 3];
double dd[1 << 3] = {inf, inf, inf, 1, inf, 2, 1, 1};
int dp[101][1 << 3];
int n, k;
vector<string> s(3);
bool valid(double x) {
for (int i = 1; i <= n; i++)
for (int is = 1; is < (1 << 3); is++) dp[i][is] = (dd[is] >= x ? __builtin_popcount(is) : 0);
for (int i = 1; i <= n; i++) {
for (int is = 0; is < (1 << 3); is++) {
bool can = true;
for (int ii = 0; ii < 3; ii++) {
if ((is & (1 << ii)) && s[ii][i] == '#') {
can = false;
break;
}
}
if (!can) continue;
for (int j = i + 2; j <= n; j++) {
for (int js = 1; js < (1 << 3); js++) {
bool ccan = true;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) && s[jj][j] == '#') {
ccan = false;
break;
}
}
if (s[0][j] == '#' && s[1][j] == '#' && s[2][j] == '#') ccan = false;
if (!ccan) continue;
if (d[i][is][j][js] >= x) {
dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js));
for (int ks = 1; ks < (1 << 3); ks++) {
if (min(d[j - 1][ks][j][js], d[i][is][j - 1][ks]) >= x) {
dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js) + __builtin_popcount(ks));
}
}
}
}
}
}
}
int mx = 0;
for (int i = 0; i <= n; i++)
for (int is = 1; is < (1 << 3); is++) {
mx = max(mx, dp[i][is]);
// cout << "dp: " << i << " " << is << " - " << dp[i][is] << "\n";
}
// cout << "x: " << x << " mx: " << mx << "\n";
if (mx >= k) return true;
else return false;
}
void solve() {
cin >> n >> k;
int scnt = 0;
for (auto& si : s) {
cin >> si;
si = '0' + si;
for (auto& sij : si)
if (sij == '#') scnt += 1;
}
if (3 * n - scnt < k) {
cout << "-1\n";
return;
}
for (int j = 1; j <= n; j++)
for (int js = 1; js < (1 << 3); js++) {
bool tmp = false;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) && s[jj][j] == '#') {
d[0][0][j][js] = 0;
tmp = true;
break;
}
}
if (!tmp) d[0][0][j][js] = dd[js];
// cout << 0 << " " << 0 << " " << j << " " << js << " : " << d[0][0][j][js] << "\n";
}
for (int i = 1; i <= n; i++) {
for (int is = 1; is < (1 << 3); is++) {
bool can = true;
for (int ii = 0; ii < 3; ii++) {
if ((is & (1 << ii)) && s[ii][i] == '#') {
can = false;
break;
}
}
if (!can) continue;
for (int j = i + 1; j <= n; j++) {
for (int js = 1; js < (1 << 3); js++) {
bool ccan = true;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) && s[jj][j] == '#') {
ccan = false;
break;
}
}
if (!ccan) continue;
d[i][is][j][js] = dd[js];
for (int ii = 0; ii < 3; ii++) {
if ((is & (1 << ii)) == 0) continue;
for (int jj = 0; jj < 3; jj++) {
if ((js & (1 << jj)) == 0) continue;
d[i][is][j][js] = min(d[i][is][j][js], sqrt(double((i - j) * (i - j) + (ii - jj) * (ii - jj))));
}
}
if (d[i][is][j][js] == inf) d[i][is][j][js] = 0;
// cout << i << " " << is << " " << j << " " << js << " : " << d[i][is][j][js] << "\n";
}
}
}
}
// valid(2.236);
double lo = 0, hi = 1000;
for (int i = 0; i < 60; i++) {
double mid = (lo + hi) / 2;
if (valid(mid)) lo = mid;
else hi = mid;
}
cout << fixed;
cout.precision(8);
cout << hi << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3988kb
input:
5 2 #.... ..... ....#
output:
4.47213595
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3984kb
input:
5 6 ##.## ##### .....
output:
1.00000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
3 4 ..# ... ...
output:
1.41421356
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
1 2 . . .
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 41ms
memory: 8556kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.02019996
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 45ms
memory: 8824kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.04079934
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 73ms
memory: 8744kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.00000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 105ms
memory: 8472kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.00000000
result:
wrong answer 1st numbers differ - expected: '1.4142140', found: '1.0000000', error = '0.2928934'