QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #477101 | #5537. Storing Eggs | karuna# | WA | 211ms | 36652kb | C++20 | 3.4kb | 2024-07-13 23:18:02 | 2024-07-13 23:18:03 |
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[3 * 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[3 * SZ][SZ][1 << 6];
int cost[3 * 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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3920kb
input:
5 2 #.... ..... ....#
output:
4.4721359550
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
5 6 ##.## ##### .....
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4052kb
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: 3680kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 2 . . .
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 28ms
memory: 25772kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.0201999594
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 29ms
memory: 25804kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.0407993410
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 115ms
memory: 31056kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 157ms
memory: 33924kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.4142135624
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #10:
score: 0
Accepted
time: 173ms
memory: 33908kb
input:
100 151 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 211ms
memory: 36652kb
input:
100 200 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 197ms
memory: 36652kb
input:
100 201 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 46ms
memory: 17012kb
input:
60 130 ............................................................ ............................................................ ............................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 33ms
memory: 30824kb
input:
100 100 .................................................................................................... #################################################################################################### .............................................................................................
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 7ms
memory: 27212kb
input:
100 51 #################################################################################################### .................................................................................................... ###########################################################################################...
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
1 2 # # #
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 12ms
memory: 26748kb
input:
99 50 ################################################################################################### ................................................................................................... ##############################################################################################...
output:
2.0000000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 19ms
memory: 27124kb
input:
100 47 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
output:
2.8284271247
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #19:
score: 0
Accepted
time: 20ms
memory: 26812kb
input:
100 43 .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
output:
2.8284271247
result:
ok found '2.8284271', expected '2.8284270', error '0.0000000'
Test #20:
score: 0
Accepted
time: 12ms
memory: 25284kb
input:
99 2 #........#............#.#.#...................................#................##..............#... ............................##...#......#...##.............#.........#..#...#............#...#..... #...............................................#..............#.....#.........#.........#........
output:
98.0051019080
result:
ok found '98.0051019', expected '98.0051020', error '0.0000000'
Test #21:
score: -100
Wrong Answer
time: 3ms
memory: 7096kb
input:
90 2 #############..######.###.##.#########.###.###########.####.############################## #...##########.#.#################.############.########################.################# ###################.###.##.####.#######..##.########.#############################.#######
output:
-1
result:
wrong answer 1st numbers differ - expected: '81.0061730', found: '-1.0000000', error = '1.0123447'