QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#143788#4195. Looking for WaldoPHarrWA 1ms3584kbC++201.7kb2023-08-21 14:44:152023-08-21 14:44:18

Judging History

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

  • [2023-08-21 14:44:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3584kb
  • [2023-08-21 14:44:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector a(n + 1, vector<array<int, 5>>(m + 1));
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= m; j++) {
            if (s[j - 1] == 'W') a[i][j][0]++;
            else if (s[j - 1] == 'A') a[i][j][1]++;
            else if (s[j - 1] == 'L') a[i][j][2]++;
            else if (s[j - 1] == 'D') a[i][j][3]++;
            else if (s[j - 1] == 'O') a[i][j][4]++;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 5; k++)
                a[i][j][k] += a[i - 1][j][k] + a[i][j - 1][k] - a[i - 1][j - 1][k];

    auto calc = [a, n, m](int r, int c, int x, int y) {
        for (int k = 0; k < 5; k++)
            if (a[x][y][k] - a[r - 1][y][k] - a[x][c - 1][k] + a[r - 1][c - 1][k] == 0) return false;
        return true;
    };
    int res = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        for (int j = 1, ans; j <= m; j++) {
            ans = LLONG_MAX;
            for (int l = i, r = n, p, f; l <= r;) {
                p = (l + r) >> 1, f = 0;
                for (int L = j, R = m, q; L <= R;) {
                    q = (L + R) >> 1;
                    if (calc(i, j, p, q)) ans = min(ans, (p - i + 1) * (q - j + 1)), f = 1, R = q - 1;
                    else L = q + 1;
                }
                if (f) res = min(res, ans), r = p - 1;
                else l = p + 1;
            }
        }
    }
    if( res == LLONG_MAX ) cout << "impossible\n";
    else cout << res << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

5 5
ABCDE
FGHIJ
KLMNO
PQRST
VWXYZ

output:

25

result:

ok single line: '25'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3508kb

input:

5 10
ABCDEABCDE
FGHIJFGHIJ
KLMNOKLMNO
PQRSTPQRST
VWXYZVWXYZ

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

5 10
WAALDLODOW
AWWLAOODOW
LOLADOWALO
ADALLLWWOL
WWOOAAAALO

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3512kb

input:

2 3
WAL
TER

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

1 260
AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO

output:

260

result:

ok single line: '260'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3520kb

input:

1 5
WALDO

output:

5

result:

ok single line: '5'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3520kb

input:

5 5
WXXAL
XALDO
XDOXX
ALXXX
DOXXX

output:

9

result:

ok single line: '9'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3532kb

input:

7 115
DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB
VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM
DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...

output:

8

result:

ok single line: '8'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3564kb

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: 0ms
memory: 3584kb

input:

2 461
ZOXPGJHVSWLVZYOPKFWBPPMFSEHNPDFUAPHPJMXDFNAOEVGFLUZLHLOUMCSYYTHNKNYXAHHJXCSXHVEONVWYKTZCYUKWRBLIRFTCWHSGWNSULYTMNQSFQQKGXTUUPRYZMDBPPEYNSTCXFCUREDPGHSIGHJGDRCIQJUNUHTCNHFLHMEEPDIXSRRDBYIJSWGJCDAVIPCUYPARKSSXHDSLYDNHZJSYXWDTBCKFYILISHVJXFLSGPVPEEICHWKENYXBAACFXLNVTNQMUENNYCSUZSWHBYXFPYPGUTFEUAR...

output:

7

result:

ok single line: '7'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

10 62
MEBVDGFNDFAVGQOYMVVJPUOPIUXNJZBVTPGMNDYKVEFITSAEKRFIGVOZSEPAFU
JYIRCBPVQCIUAMGHUTVOEDNLVDTNBXUAMMJFZQPVUOKYGILFEVEKRYOKJCZKSX
IVNCDWFOUQKLEBOKKDKAXOKHFKPRUUAMSUDIBBWRICUALRRGAKMADEKSRWASKK
EVUMONXCMASAGLDEQAKFFJYPMVLNRRDXVFJJLBUYAUCRLUXBQWCVHNLSGZOIUW
XFKUOZQJHLAWSUPLBRBFJQXHAFMSBCMFUVDLKEFDLN...

output:

6

result:

ok single line: '6'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3508kb

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: -100
Wrong Answer
time: 1ms
memory: 3476kb

input:

9 8
WSWLWZTQ
SEIXFVUV
VRBEKFKR
EAKHTYEP
CIYZFNNE
XHFBOKWE
DXFWSGRK
ONFJKUQY
KUJQCJME

output:

35

result:

wrong answer 1st lines differ - expected: '32', found: '35'