QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136475 | #4195. Looking for Waldo | RetiredButNotTired# | WA | 1ms | 3540kb | C++20 | 1.6kb | 2023-08-08 20:26:40 | 2023-08-08 20:26:40 |
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' };
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;
};
int sq = sqrt(h * w) + 5;
ll ans = 1e18;
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());
}
}
}
cout << (ans <= h * w ? ans : -1) << "\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: 1ms
memory: 3540kb
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: 1ms
memory: 3532kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3528kb
input:
2 3 WAL TER
output:
-1
result:
wrong answer 1st lines differ - expected: 'impossible', found: '-1'