QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426954#4195. Looking for Waldorania__#WA 0ms3676kbC++203.0kb2024-06-01 02:48:232024-06-01 02:48:23

Judging History

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

  • [2024-06-01 02:48:23]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3676kb
  • [2024-06-01 02:48:23]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>>pref[5];
array<int,5> get_sum(int col,int l,int r)
{
    array<int,5>a;
    for(int i=0; i<5; i++)
    {
        if(l == 0)a[i]=pref[i][r][col];
        else a[i]=pref[i][r][col] - pref[i][l-1][col];
    }
    return a;
}
void solve()
{
    int n,m;
    cin>>n>>m;
    char grid[min(n,m)][max(n,m)];
    bool f1=0,f2=0,f3=0,f4=0,f5=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(n>m)cin>>grid[j][i];
            else cin>>grid[i][j];
            if(grid[i][j]=='W')f1=1;
            if(grid[i][j]=='A')f2=1;
            if(grid[i][j]=='L')f3=1;
            if(grid[i][j]=='D')f4=1;
            if(grid[i][j]=='O')f5=1;
        }
    }

    if((f1&f2&f3&f4&f5)==0)
    {
        cout<<"impossible";
        return;
    }
    if(n>m)
        swap(n,m);
    vector<int>v;
    for(int i=0; i<m; i++)v.push_back(0);
    vector<vector<int>>v2;
    for(int i=0; i<n; i++)v2.push_back(v);
    for(int i=0; i<5; i++)
    {
        pref[i] = v2;
    }
    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cout<<grid[i][j];
        }
        cout<<endl;
    }*/

    int hsh[1000];
    memset(hsh,-1,sizeof(hsh));
    hsh['W']=0;
    hsh['A']=1;
    hsh['L']=2;
    hsh['D']=3;
    hsh['O']=4;
    for(int j=0; j<m; j++)
    {
        for(int i=0; i<n; i++)
        {
            for(int k=0; k<5; k++)
                if(i)pref[k][i][j]=pref[k][i-1][j];
            if(hsh[grid[i][j]]!=-1)
            {
                pref[hsh[grid[i][j]]][i][j]++;
            }

        }
    }

    int ans=1e18;
    for(int row_start = 0; row_start<n; row_start++)
    {
        for(int row_end = row_start; row_end<n; row_end++)
        {
            int freq[5]={};
            int left_ptr=0;
            for(int i=0;i<m;i++)
            {
                array<int,5>aa = get_sum(i,row_start,row_end);
                for(int k=0;k<5;k++)
                {
                    freq[k]+=aa[k];
                }
                bool valid=1;
                for(int k=0;k<5;k++)
                {
                    if(freq[k] == 0)
                    {
                        valid=0;
                        break;
                    }
                }
                while(left_ptr <=i && valid)
                {
                    ans=min(ans,(i-left_ptr+1)*(row_end-row_start+1));
                    array<int,5>bb = get_sum(left_ptr,row_start,row_end);
                    for(int k=0;k<5;k++)
                    {
                        freq[k]-=bb[k];
                        if(freq[k] == 0)valid=0;
                    }
                    left_ptr++;
                }

            }

        }
    }
    cout<<ans<<endl;


}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 5
ABCDE
FGHIJ
KLMNO
PQRST
VWXYZ

output:

25

result:

ok single line: '25'

Test #2:

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

input:

5 10
ABCDEABCDE
FGHIJFGHIJ
KLMNOKLMNO
PQRSTPQRST
VWXYZVWXYZ

output:

20

result:

ok single line: '20'

Test #3:

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

input:

5 10
WAALDLODOW
AWWLAOODOW
LOLADOWALO
ADALLLWWOL
WWOOAAAALO

output:

5

result:

ok single line: '5'

Test #4:

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

input:

2 3
WAL
TER

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

1 260
AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO

output:

260

result:

ok single line: '260'

Test #6:

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

input:

1 5
WALDO

output:

5

result:

ok single line: '5'

Test #7:

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

input:

5 5
WXXAL
XALDO
XDOXX
ALXXX
DOXXX

output:

9

result:

ok single line: '9'

Test #8:

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

input:

7 115
DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB
VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM
DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...

output:

8

result:

ok single line: '8'

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3660kb

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:

impossible

result:

wrong answer 1st lines differ - expected: '11', found: 'impossible'