QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#145172#4195. Looking for Waldo2468216537WA 1ms3600kbC++172.0kb2023-08-21 23:04:322023-08-21 23:04:36

Judging History

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

  • [2023-08-21 23:04:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3600kb
  • [2023-08-21 23:04:32]
  • 提交

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'