QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136487 | #4195. Looking for Waldo | RetiredButNotTired# | TL | 4ms | 3700kb | C++20 | 3.0kb | 2023-08-08 20:50:02 | 2023-08-08 20:50:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;
void solve() {
int h, w;
cin >> h >> w;
vector<string> v(h);
for (auto& u : v) cin >> u;
vector<char> imp = { 'W', 'A', 'L', 'D', 'O' };
int sq = sqrt(h * w) + 5;
ll ans = 1e18;
{
vector<vector<vector<int>>> nxt(5, vector<vector<int>>(h, vector<int>(w, w)));
for (int k = 0; k < 5; k++)
for (int i = 0; i < h; i++)
for (int j = w - 2; j >= 0; --j) nxt[k][i][j] = (v[i][j + 1] == imp[k] ? j + 1 : nxt[k][i][j + 1]);
auto find_height = [&](int row, int col, int k) {
if (v[row][col] == imp[k]) return 1LL;
if (nxt[k][row][col] == w) return (ll)1e15;
return nxt[k][row][col] - col + 1LL;
};
for (int col = 0; col < w; col++) {
for (int len = 1; len <= min(h, sq); len++) {
vector<set<pair<ll, int>>> x(5);
for (int k = 0; k < 5; k++)
for (int row = 0; row < len; row++)
x[k].emplace(find_height(row, col, k), row);
auto find_min = [&]() {
ll mx = -1e18;
for (int k = 0; k < 5; k++) mx = max(mx, x[k].begin()->first);
return mx;
};
ans = min(ans, len * find_min());
for (int row = len; row < h; row++) {
for (int k = 0; k < 5; k++) x[k].erase(make_pair(find_height(row - len, col, k), row - len));
for (int k = 0; k < 5; k++) x[k].emplace(find_height(row, col, k), row);
ans = min(ans, len * find_min());
}
}
}
}
vector<string> new_v(w);
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
new_v[j].push_back(v[i][j]);
swap(h, w);
v = new_v;
{
vector<vector<vector<int>>> nxt(5, vector<vector<int>>(h, vector<int>(w, w)));
for (int k = 0; k < 5; k++)
for (int i = 0; i < h; i++)
for (int j = w - 2; j >= 0; --j) nxt[k][i][j] = (v[i][j + 1] == imp[k] ? j + 1 : nxt[k][i][j + 1]);
auto find_height = [&](int row, int col, int k) {
if (v[row][col] == imp[k]) return 1LL;
if (nxt[k][row][col] == w) return (ll)1e15;
return nxt[k][row][col] - col + 1LL;
};
for (int col = 0; col < w; col++) {
for (int len = 1; len <= min(h, sq); len++) {
vector<deque<int>> x(5);
auto add = [&](int k, int new_row) {
while (!x[k].empty() && find_height(x[k].back(), col, k) > find_height(new_row, col, k))
x[k].pop_back();
x[k].push_back(new_row);
};
for (int k = 0; k < 5; k++)
for (int row = 0; row < len; row++)
add(k, row);
auto find_min = [&]() {
ll mx = -1e18;
for (int k = 0; k < 5; k++) mx = max(mx, find_height(x[k].front(), col, k));
return mx;
};
ans = min(ans, len * find_min());
for (int row = len; row < h; row++) {
for (int k = 0; k < 5; k++) if (x[k].front() <= row - len) x[k].pop_front();
for (int k = 0; k < 5; k++) add(k, row);
ans = min(ans, len * find_min());
}
}
}
}
cout << (ans <= h * w ? to_string(ans) : "impossible") << "\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
tt = 1, tc = 1; // cin >> tt;
while (tt--) solve(), tc++;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3480kb
input:
5 5 ABCDE FGHIJ KLMNO PQRST VWXYZ
output:
25
result:
ok single line: '25'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3552kb
input:
5 10 ABCDEABCDE FGHIJFGHIJ KLMNOKLMNO PQRSTPQRST VWXYZVWXYZ
output:
20
result:
ok single line: '20'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
2 3 WAL TER
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
1 260 AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO
output:
260
result:
ok single line: '260'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
1 5 WALDO
output:
5
result:
ok single line: '5'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3540kb
input:
5 5 WXXAL XALDO XDOXX ALXXX DOXXX
output:
9
result:
ok single line: '9'
Test #8:
score: 0
Accepted
time: 4ms
memory: 3604kb
input:
7 115 DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3616kb
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: 3ms
memory: 3604kb
input:
2 461 ZOXPGJHVSWLVZYOPKFWBPPMFSEHNPDFUAPHPJMXDFNAOEVGFLUZLHLOUMCSYYTHNKNYXAHHJXCSXHVEONVWYKTZCYUKWRBLIRFTCWHSGWNSULYTMNQSFQQKGXTUUPRYZMDBPPEYNSTCXFCUREDPGHSIGHJGDRCIQJUNUHTCNHFLHMEEPDIXSRRDBYIJSWGJCDAVIPCUYPARKSSXHDSLYDNHZJSYXWDTBCKFYILISHVJXFLSGPVPEEICHWKENYXBAACFXLNVTNQMUENNYCSUZSWHBYXFPYPGUTFEUAR...
output:
7
result:
ok single line: '7'
Test #11:
score: 0
Accepted
time: 4ms
memory: 3592kb
input:
10 62 MEBVDGFNDFAVGQOYMVVJPUOPIUXNJZBVTPGMNDYKVEFITSAEKRFIGVOZSEPAFU JYIRCBPVQCIUAMGHUTVOEDNLVDTNBXUAMMJFZQPVUOKYGILFEVEKRYOKJCZKSX IVNCDWFOUQKLEBOKKDKAXOKHFKPRUUAMSUDIBBWRICUALRRGAKMADEKSRWASKK EVUMONXCMASAGLDEQAKFFJYPMVLNRRDXVFJJLBUYAUCRLUXBQWCVHNLSGZOIUW XFKUOZQJHLAWSUPLBRBFJQXHAFMSBCMFUVDLKEFDLN...
output:
6
result:
ok single line: '6'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3492kb
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: 0
Accepted
time: 1ms
memory: 3552kb
input:
9 8 WSWLWZTQ SEIXFVUV VRBEKFKR EAKHTYEP CIYZFNNE XHFBOKWE DXFWSGRK ONFJKUQY KUJQCJME
output:
32
result:
ok single line: '32'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
29 6 BVROIF KSZROD RWYYFV CHKFXG NANVXJ KSCOCH QIDLUT KPPHPF HGWTTN CCOJEV QZPPHL LZAUXY XICHTP RSMYEI MJEWDF IYRXBW GLJVXM DOONIH OPMUZW YYYLSE SGSPVZ WVORGQ BTWOIS NPIQKT CORXPN KMNLGT QTMVSW WFOJNS GQQZKO
output:
12
result:
ok single line: '12'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
6 30 YIEWUARANVJHLMMFIBBGKNDINMKCIH MYGXZOGUNRHSICKEECSLTIFSEDFDYO OENJCWJZMAEUJLJOEHPBSCKUCGMBPO GCETCKSYVVOFSTAIODZDVDHYGBHQPP RTKBTULQAGCFHEIYSYKGJNPCYFNNTD UTBYRFXJGQIBREELOWWVMKUBEQDINX
output:
12
result:
ok single line: '12'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
27 6 DXKWIJ SQFIKD ZOBIUI UTQRJN TUVCQZ CBRXHF ULHYRV QEQYBE LVJZNT NDAJAQ NTTRSY ETAYBI LWLWHA DCXBVH HKLOQT DLICSA ZNIROE MJRAVY RZBDOE TIIQDG OTZAOV WZNBBN GXSSXT NBXKTJ VTWNAU LXHDLS PBTUCR
output:
14
result:
ok single line: '14'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3516kb
input:
21 8 OZSOIHXZ HMQRLUXE HIVETDEP DQJCTXNE SXDOHCYG TFYKEFJW TJGXULLS PMEJGSEF UYAHBHKS WALAUWUJ DQXLTFVG NVHTNPNA ILITJIOS NNFUIMPX BCUYEIFL VJWISWVQ HZNPZZJF HIJPMRJI FCXYRPSA WVOKEXQB GHYDZKBM
output:
16
result:
ok single line: '16'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
5 5 LAXXW ODLAX XXODX XXXLA XXXOD
output:
9
result:
ok single line: '9'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
5 5 XXXOD XXXLA XXODX ODLAX LAXXW
output:
9
result:
ok single line: '9'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
5 5 DOXXX ALXXX XDOXX XALDO WXXAL
output:
9
result:
ok single line: '9'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
9 9 XXXODOXXX XXXLALXXX XXODXDOXX ODLAXALDO LAXXWXXAL ODLAXALDO XXODXDOXX XXXLALXXX XXXODOXXX
output:
9
result:
ok single line: '9'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
1 1 W
output:
impossible
result:
ok single line: 'impossible'
Test #23:
score: -100
Time Limit Exceeded
input:
176 472 KUMYIMXYCXUKCQXPDEOURBXYMTQVXOCYNZYCPKNAYWZMKMKBDYCCLJCWHRWKFAVYRDDQBNONSIQEKWJVUUGICMHFXTRUGLVHELGGSSFMEWXMWKUVMJHBSECGUFVXPKHJGDLNCYWPAAAOAVNKUXXKMLXJSLTJUAJJWVZMJCKTLDRELSUACYKBNRFFZMJODJQQYRTAFUJVENRLBFCQHKCSDBYSMYOYBUAXNDYCSSFYRGTLSMDOEVOWPXPBFBAQWFWEIGOEPUQTGTXTCLOCTUXKEWKFRKVSEPVIMFUA...