QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136475#4195. Looking for WaldoRetiredButNotTired#WA 1ms3540kbC++201.6kb2023-08-08 20:26:402023-08-08 20:26:40

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-08 20:26:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3540kb
  • [2023-08-08 20:26:40]
  • 提交

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++;
}

Details

Tip: Click on the bar to expand more detailed information

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'