QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #477095 | #5537. Storing Eggs | karuna# | RE | 114ms | 31180kb | C++20 | 3.4kb | 2024-07-13 23:16:56 | 2024-07-13 23:16:57 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int SZ = 110;
int n, s, a[3][SZ];
int dp[SZ][SZ][1 << 6], blk[SZ];
int ds(pii p, pii q) {
return (p.ff - q.ff) * (p.ff - q.ff) + (p.ss - q.ss) * (p.ss - q.ss);
}
int dp2[SZ][SZ][1 << 6];
int cost[SZ][SZ][1 << 6][1 << 6];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> s;
for (int t = 0; t < 3; t++) {
string S;
cin >> S;
for (int i = 1; i <= n; i++) {
if (S[i - 1] == '#') a[t][i] = true;
}
}
a[0][0] = a[1][0] = a[2][0] = true;
for (int i = 1; i <= n; i++) {
for (int t = 0; t < 3; t++) blk[i] ^= (1 - a[t][i]) << t;
for (int t = 0; t < 3; t++) blk[i] ^= (1 - a[t][i - 1]) << (t + 3);
}
dp[0][0][0] = 1e9;
for (int k = 1; k <= s; k++) {
for (int i = 1; i <= n; i++) {
for (int msk = 0; msk < (1 << 6); msk++) {
if ((blk[i] & msk) != msk) continue;
// case 1. from i - 1
if (k >= __builtin_popcount(msk & 7) && __builtin_popcount(msk & 7) != 0) {
for (int up = 0; up < (1 << 3); up++) {
int prv = (msk >> 3) | (up << 3);
if ((blk[i - 1] & prv) != prv) continue;
if (cost[i][i - 1][msk][prv] == 0) {
vector<pii> L, R;
for (int t = 0; t < 3; t++) if (msk >> t & 1) R.push_back({t, i});
for (int t = 0; t < 3; t++) if (prv >> t & 1) L.push_back({t, i - 1});
for (int t = 0; t < 3; t++) if (prv >> (t + 3) & 1) L.push_back({t, i - 2});
int minv = 1e9;
for (int i = 0; i < R.size(); i++) for (int j = 0; j < i; j++) {
minv = min(minv, ds(R[i], R[j]));
}
for (pii p : L) for (pii q : R) {
minv = min(minv, ds(p, q));
}
cost[i][i - 1][msk][prv] = minv;
}
dp[k][i][msk] = max(dp[k][i][msk], min(dp[k - __builtin_popcount(msk & 7)][i - 1][prv], cost[i][i - 1][msk][prv]));
}
}
// case 2. from before i - 1
if ((msk & 56) == 0 && k >= __builtin_popcount(msk) && __builtin_popcount(msk) != 0) {
for (int j = 0; j < i - 1; j++) {
for (int prv = 0; prv < (1 << 3); prv++) {
if ((blk[j] & prv) != prv) continue;
if (cost[i][j][msk][prv] == 0) {
vector<pii> L, R;
for (int t = 0; t < 3; t++) if (msk >> t & 1) R.push_back({t, i});
for (int t = 0; t < 3; t++) if (msk >> (t + 3) & 1) R.push_back({t, i - 1});
for (int t = 0; t < 3; t++) if (prv >> t & 1) L.push_back({t, j});
for (int t = 0; t < 3; t++) if (prv >> (t + 3) & 1) L.push_back({t, j - 1});
int minv = 1e9;
for (int i = 0; i < R.size(); i++) for (int j = 0; j < i; j++) {
minv = min(minv, ds(R[i], R[j]));
}
for (pii p : L) for (pii q : R) {
minv = min(minv, ds(p, q));
}
cost[i][j][msk][prv] = minv;
}
dp[k][i][msk] = max(dp[k][i][msk], min(dp2[k - __builtin_popcount(msk)][j][prv], cost[i][j][msk][prv]));
}
}
}
}
for (int msk = 0; msk < (1 << 6); msk++) {
dp2[k][i][msk & 7] = max(dp2[k][i][msk & 7], dp[k][i][msk]);
}
}
}
int ans = 0;
for (int i = 0; i <= n; i++) {
for (int msk = 0; msk < (1 << 6); msk++) {
ans = max(ans, dp[s][i][msk]);
}
}
if (ans == 0) return !(cout << "-1\n");
cout.precision(10);
cout << fixed << sqrt(ans) << '\n';
}
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.4721359550
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
5 6 ##.## ##### .....
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
3 4 ..# ... ...
output:
1.4142135624
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
1 2 . . .
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 22ms
memory: 25764kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.0201999594
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 17ms
memory: 25824kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.0407993410
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 114ms
memory: 31180kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: -100
Runtime Error
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................