QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185261 | #4195. Looking for Waldo | rgnerdplayer# | RE | 0ms | 3824kb | C++20 | 2.1kb | 2023-09-21 20:12:41 | 2023-09-21 20:12:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto solve = [&]() {
int n, m;
cin >> n >> m;
bool trans = false;
if (n > m) {
trans = true;
swap(n, m);
}
vector a(n, string(m, '?'));
for (int i = 0; i < min(n, m); i++) {
for (int j = 0; j < max(n, m); j++) {
if (!trans) {
cin >> a[i][j];
} else {
cin >> a[j][i];
}
}
}
string code = "WALDO";
vector f(5, vector(n + 1, vector<int>(m + 1)));
for (int c = 0; c < 5; c++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
f[c][i + 1][j + 1] = f[c][i + 1][j] + f[c][i][j + 1] - f[c][i][j] + (a[i][j] == code[c]);
}
}
}
auto sum = [&](int c, int x1, int y1, int x2, int y2) {
return f[c][x2 + 1][y2 + 1] - f[c][x1][y2 + 1] - f[c][x2 + 1][y1] + f[c][x1][y1];
};
auto check = [&](int x1, int y1, int x2, int y2) {
for (int c = 0; c < 5; c++) {
if (sum(c, x1, y1, x2, y2) == 0) {
return false;
}
}
return true;
};
constexpr int INF = 1e9;
int ans = INF;
for (int x1 = 0; x1 < n; x1++) {
for (int x2 = x1; x2 < n; x2++) {
for (int y1 = 0, y2 = 0; y1 < m; y1++) {
y2 = max(y2, y1);
while (y2 < m && !check(x1, y1, x2, y2)) {
y2++;
}
if (y2 < m) {
ans = min(ans, (x2 - x1 + 1) * (y2 - y1 + 1));
}
}
}
}
if (ans == INF) {
cout << "impossible\n";
} else {
cout << ans << '\n';
}
};
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
5 5 ABCDE FGHIJ KLMNO PQRST VWXYZ
output:
25
result:
ok single line: '25'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
5 10 ABCDEABCDE FGHIJFGHIJ KLMNOKLMNO PQRSTPQRST VWXYZVWXYZ
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 3 WAL TER
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 260 AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO
output:
260
result:
ok single line: '260'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 5 WALDO
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
5 5 WXXAL XALDO XDOXX ALXXX DOXXX
output:
9
result:
ok single line: '9'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
7 115 DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...
output:
8
result:
ok single line: '8'
Test #9:
score: -100
Runtime Error
input:
43 6 MSKXQI PGFKAO YZSLPS LVMBUX QQJWVW GWVLPM HDBTRG WKHMGP RLGDEB TXYZEY LQRDJI IFIJZU STLLPN HDJOID NTIAZG KHQVHO UBUERZ PWBOBI UTIEJW KWEPPZ TVWEBQ JVFXYB QHKYCG DXJXMD BZGFOV RRHFKI PZUCBJ NUOPLE ZWVFVP NACTWZ XAJRUG XOBZIC EGHUGF TODGGA AYQHYD QPVLIQ HJLKOV WTRZJJ AXSPON LWRXIG VPUZOR ZDZQXK C...