QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185257#4195. Looking for Waldorgnerdplayer#RE 0ms3620kbC++202.1kb2023-09-21 20:09:262023-09-21 20:09:28

Judging History

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

  • [2023-09-21 20:09:28]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3620kb
  • [2023-09-21 20:09:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    auto solve = [&]() {
        int n, m;
        cin >> n >> m;

        bool trans = false;

        if (n > m) {
            trans = true;
            swap(n, m);
        }

        vector a(n, string(m, '?'));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!trans) {
                    cin >> a[i][j];
                } else {
                    cin >> a[j][i];
                }
            }
        }

        string code = "WALDO";
        vector f(5, vector(n + 1, vector<int>(m + 1)));
        
        for (int c = 0; c < 5; c++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    f[c][i + 1][j + 1] = f[c][i + 1][j] + f[c][i][j + 1] - f[c][i][j] + (a[i][j] == code[c]);
                }
            }
        }

        auto sum = [&](int c, int x1, int y1, int x2, int y2) {
            return f[c][x2 + 1][y2 + 1] - f[c][x1][y2 + 1] - f[c][x2 + 1][y1] + f[c][x1][y1];
        };

        auto check = [&](int x1, int y1, int x2, int y2) {
            for (int c = 0; c < 5; c++) {
                if (sum(c, x1, y1, x2, y2) == 0) {
                    return false;
                }
            }
            return true;
        };

        constexpr int INF = 1e9;
        int ans = INF;

        for (int x1 = 0; x1 < n; x1++) {
            for (int x2 = x1; x2 < n; x2++) {
                for (int y1 = 0, y2 = 0; y1 < m; y1++) {
                    y2 = max(y2, y1);
                    while (y2 < m && !check(x1, y1, x2, y2)) {
                        y2++;
                    }
                    if (y2 < m) {
                        ans = min(ans, (x2 - x1 + 1) * (y2 - y1 + 1));
                    }
                }
            }
        }

        if (ans == INF) {
            cout << "impossible\n";
        } else {
            cout << ans << '\n';
        }
    };

    solve();

    return 0;
}


詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

5 5
ABCDE
FGHIJ
KLMNO
PQRST
VWXYZ

output:

25

result:

ok single line: '25'

Test #2:

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

input:

5 10
ABCDEABCDE
FGHIJFGHIJ
KLMNOKLMNO
PQRSTPQRST
VWXYZVWXYZ

output:

20

result:

ok single line: '20'

Test #3:

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

input:

5 10
WAALDLODOW
AWWLAOODOW
LOLADOWALO
ADALLLWWOL
WWOOAAAALO

output:

5

result:

ok single line: '5'

Test #4:

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

input:

2 3
WAL
TER

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

1 260
AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO

output:

260

result:

ok single line: '260'

Test #6:

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

input:

1 5
WALDO

output:

5

result:

ok single line: '5'

Test #7:

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

input:

5 5
WXXAL
XALDO
XDOXX
ALXXX
DOXXX

output:

9

result:

ok single line: '9'

Test #8:

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

input:

7 115
DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB
VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM
DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...

output:

8

result:

ok single line: '8'

Test #9:

score: -100
Runtime Error

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:


result: