QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#143788 | #4195. Looking for Waldo | PHarr | WA | 1ms | 3584kb | C++20 | 1.7kb | 2023-08-21 14:44:15 | 2023-08-21 14:44:18 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector a(n + 1, vector<array<int, 5>>(m + 1));
string s;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 1; j <= m; j++) {
if (s[j - 1] == 'W') a[i][j][0]++;
else if (s[j - 1] == 'A') a[i][j][1]++;
else if (s[j - 1] == 'L') a[i][j][2]++;
else if (s[j - 1] == 'D') a[i][j][3]++;
else if (s[j - 1] == 'O') a[i][j][4]++;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = 0; k < 5; k++)
a[i][j][k] += a[i - 1][j][k] + a[i][j - 1][k] - a[i - 1][j - 1][k];
auto calc = [a, n, m](int r, int c, int x, int y) {
for (int k = 0; k < 5; k++)
if (a[x][y][k] - a[r - 1][y][k] - a[x][c - 1][k] + a[r - 1][c - 1][k] == 0) return false;
return true;
};
int res = LLONG_MAX;
for (int i = 1; i <= n; i++) {
for (int j = 1, ans; j <= m; j++) {
ans = LLONG_MAX;
for (int l = i, r = n, p, f; l <= r;) {
p = (l + r) >> 1, f = 0;
for (int L = j, R = m, q; L <= R;) {
q = (L + R) >> 1;
if (calc(i, j, p, q)) ans = min(ans, (p - i + 1) * (q - j + 1)), f = 1, R = q - 1;
else L = q + 1;
}
if (f) res = min(res, ans), r = p - 1;
else l = p + 1;
}
}
}
if( res == LLONG_MAX ) cout << "impossible\n";
else cout << res << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
5 5 ABCDE FGHIJ KLMNO PQRST VWXYZ
output:
25
result:
ok single line: '25'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
5 10 ABCDEABCDE FGHIJFGHIJ KLMNOKLMNO PQRSTPQRST VWXYZVWXYZ
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
2 3 WAL TER
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
1 260 AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO
output:
260
result:
ok single line: '260'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
1 5 WALDO
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
5 5 WXXAL XALDO XDOXX ALXXX DOXXX
output:
9
result:
ok single line: '9'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
7 115 DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3564kb
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...
output:
11
result:
ok single line: '11'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 461 ZOXPGJHVSWLVZYOPKFWBPPMFSEHNPDFUAPHPJMXDFNAOEVGFLUZLHLOUMCSYYTHNKNYXAHHJXCSXHVEONVWYKTZCYUKWRBLIRFTCWHSGWNSULYTMNQSFQQKGXTUUPRYZMDBPPEYNSTCXFCUREDPGHSIGHJGDRCIQJUNUHTCNHFLHMEEPDIXSRRDBYIJSWGJCDAVIPCUYPARKSSXHDSLYDNHZJSYXWDTBCKFYILISHVJXFLSGPVPEEICHWKENYXBAACFXLNVTNQMUENNYCSUZSWHBYXFPYPGUTFEUAR...
output:
7
result:
ok single line: '7'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
10 62 MEBVDGFNDFAVGQOYMVVJPUOPIUXNJZBVTPGMNDYKVEFITSAEKRFIGVOZSEPAFU JYIRCBPVQCIUAMGHUTVOEDNLVDTNBXUAMMJFZQPVUOKYGILFEVEKRYOKJCZKSX IVNCDWFOUQKLEBOKKDKAXOKHFKPRUUAMSUDIBBWRICUALRRGAKMADEKSRWASKK EVUMONXCMASAGLDEQAKFFJYPMVLNRRDXVFJJLBUYAUCRLUXBQWCVHNLSGZOIUW XFKUOZQJHLAWSUPLBRBFJQXHAFMSBCMFUVDLKEFDLN...
output:
6
result:
ok single line: '6'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
24 4 PTLR CFSQ WJRS KMOA UTUI LLBX OMJV VAPR OHEA ETZA YGJA XWYF AHYC ZRXT WBQG QSQR JBWY VQTC ZGFF USJI APJH TTGF PVKC JNOU
output:
impossible
result:
ok single line: 'impossible'
Test #13:
score: -100
Wrong Answer
time: 1ms
memory: 3476kb
input:
9 8 WSWLWZTQ SEIXFVUV VRBEKFKR EAKHTYEP CIYZFNNE XHFBOKWE DXFWSGRK ONFJKUQY KUJQCJME
output:
35
result:
wrong answer 1st lines differ - expected: '32', found: '35'