QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#145172 | #4195. Looking for Waldo | 2468216537 | WA | 1ms | 3600kb | C++17 | 2.0kb | 2023-08-21 23:04:32 | 2023-08-21 23:04:36 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)x.size())
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define left sfad
#define right dsfa
using namespace std;
using ll = long long;
using PII = pair<int,int>;
using db = double;
mt19937 mrand(random_device{}());
const int N = 500010, M = 26, mod = 1e9 + 7,inf = 1e9;
int id[200];
int main(){
IOS
int n,m;
cin >> n >> m;
memset(id,-1,sizeof id);
id['A'] = 0,id['D'] = 1,id['L'] = 2,id['O'] = 3,id['W'] = 4;
vector g(n,vector<char> (m));
rep(i,0,n) rep(j,0,m) cin >> g[i][j];
if (n < m) {
vector<vector<char>> f(m);
rep(i,0,m) rep(j,0,n) f[i].pb(g[j][i]);
g = f;
swap(n,m);
}
int res = 1e9;
for (int i = 0;i < m - 1;i++){
vector<array<int,5>> a(n);
for (int j = i;j < m;j++){
int len = n + 1;
array<int,5> st{0,0,0,0,0};
for (int k = 0,l = 0;k < n;k++) {
if (id[g[k][j]] != -1){
int v = id[g[k][j]];
a[k][v]++;
}
rep(r,0,5) st[r] += a[k][r];
auto check = [&](int x){
auto t = st;
rep(r,0,5) {
t[r] -= a[x][r];
if (t[r] <= 0) return false;
}
st = t;
return true;
};
while (l < k && check(l)) l++;
int ok = 1;
rep(r,0,5) if (st[r] <= 0) ok = 0;
if (ok) {
len = min(len,k - l + 1);
}
}
if (len <= n) res = min(res,(j - i + 1)*len);
}
}
if (res >= 1e9) cout << "impossible\n";
else cout << res << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3536kb
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: 3600kb
input:
5 10 WAALDLODOW AWWLAOODOW LOLADOWALO ADALLLWWOL WWOOAAAALO
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
2 3 WAL TER
output:
impossible
result:
ok single line: 'impossible'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3512kb
input:
1 260 AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO
output:
impossible
result:
wrong answer 1st lines differ - expected: '260', found: 'impossible'