QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#426957#4195. Looking for Waldorania__#AC ✓278ms8084kbC++203.1kb2024-06-01 02:50:322024-06-01 02:50:32

Judging History

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

  • [2024-06-01 02:50:32]
  • 评测
  • 测评结果:AC
  • 用时:278ms
  • 内存:8084kb
  • [2024-06-01 02:50:32]
  • 提交

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(n>m)
        swap(n,m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;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;
    }
    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();
    }

}

詳細信息

Test #1:

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

input:

5 5
ABCDE
FGHIJ
KLMNO
PQRST
VWXYZ

output:

25

result:

ok single line: '25'

Test #2:

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

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: 3792kb

input:

2 3
WAL
TER

output:

impossible

result:

ok single line: 'impossible'

Test #5:

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

input:

1 260
AWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWLDO

output:

260

result:

ok single line: '260'

Test #6:

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

input:

1 5
WALDO

output:

5

result:

ok single line: '5'

Test #7:

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

input:

5 5
WXXAL
XALDO
XDOXX
ALXXX
DOXXX

output:

9

result:

ok single line: '9'

Test #8:

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

input:

7 115
DVGTNMMOMTPGLREEHPNWWOVARKFSSAQNWBBSUIUXDTRLZXHJAVOQPZWNJDMCBJRVSJNTUSOGUYKBWVUEDGJJJZRIJAJONHUSUJVGMYRDNRKZZLYOKRB
VVPSQMSDLFLEHIBTFMMRAWJFZTRVXOQJCNMPLYMWAXRXPXQWEDMWYTCQQBDGUACGWIQBIIRMTCYBQPKNWPYIRPHEIFHCPKYTVRSBBXUXVOCSLPJFRWM
DUSXXJPYFRNCGGDJPDVDXGKLDBABDGMWBELWYWMQMQCRAHINEYSMTLXGUOBGAC...

output:

8

result:

ok single line: '8'

Test #9:

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

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: 3808kb

input:

2 461
ZOXPGJHVSWLVZYOPKFWBPPMFSEHNPDFUAPHPJMXDFNAOEVGFLUZLHLOUMCSYYTHNKNYXAHHJXCSXHVEONVWYKTZCYUKWRBLIRFTCWHSGWNSULYTMNQSFQQKGXTUUPRYZMDBPPEYNSTCXFCUREDPGHSIGHJGDRCIQJUNUHTCNHFLHMEEPDIXSRRDBYIJSWGJCDAVIPCUYPARKSSXHDSLYDNHZJSYXWDTBCKFYILISHVJXFLSGPVPEEICHWKENYXBAACFXLNVTNQMUENNYCSUZSWHBYXFPYPGUTFEUAR...

output:

7

result:

ok single line: '7'

Test #11:

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

input:

10 62
MEBVDGFNDFAVGQOYMVVJPUOPIUXNJZBVTPGMNDYKVEFITSAEKRFIGVOZSEPAFU
JYIRCBPVQCIUAMGHUTVOEDNLVDTNBXUAMMJFZQPVUOKYGILFEVEKRYOKJCZKSX
IVNCDWFOUQKLEBOKKDKAXOKHFKPRUUAMSUDIBBWRICUALRRGAKMADEKSRWASKK
EVUMONXCMASAGLDEQAKFFJYPMVLNRRDXVFJJLBUYAUCRLUXBQWCVHNLSGZOIUW
XFKUOZQJHLAWSUPLBRBFJQXHAFMSBCMFUVDLKEFDLN...

output:

6

result:

ok single line: '6'

Test #12:

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

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: 0
Accepted
time: 0ms
memory: 3756kb

input:

9 8
WSWLWZTQ
SEIXFVUV
VRBEKFKR
EAKHTYEP
CIYZFNNE
XHFBOKWE
DXFWSGRK
ONFJKUQY
KUJQCJME

output:

32

result:

ok single line: '32'

Test #14:

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

input:

29 6
BVROIF
KSZROD
RWYYFV
CHKFXG
NANVXJ
KSCOCH
QIDLUT
KPPHPF
HGWTTN
CCOJEV
QZPPHL
LZAUXY
XICHTP
RSMYEI
MJEWDF
IYRXBW
GLJVXM
DOONIH
OPMUZW
YYYLSE
SGSPVZ
WVORGQ
BTWOIS
NPIQKT
CORXPN
KMNLGT
QTMVSW
WFOJNS
GQQZKO

output:

12

result:

ok single line: '12'

Test #15:

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

input:

6 30
YIEWUARANVJHLMMFIBBGKNDINMKCIH
MYGXZOGUNRHSICKEECSLTIFSEDFDYO
OENJCWJZMAEUJLJOEHPBSCKUCGMBPO
GCETCKSYVVOFSTAIODZDVDHYGBHQPP
RTKBTULQAGCFHEIYSYKGJNPCYFNNTD
UTBYRFXJGQIBREELOWWVMKUBEQDINX

output:

12

result:

ok single line: '12'

Test #16:

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

input:

27 6
DXKWIJ
SQFIKD
ZOBIUI
UTQRJN
TUVCQZ
CBRXHF
ULHYRV
QEQYBE
LVJZNT
NDAJAQ
NTTRSY
ETAYBI
LWLWHA
DCXBVH
HKLOQT
DLICSA
ZNIROE
MJRAVY
RZBDOE
TIIQDG
OTZAOV
WZNBBN
GXSSXT
NBXKTJ
VTWNAU
LXHDLS
PBTUCR

output:

14

result:

ok single line: '14'

Test #17:

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

input:

21 8
OZSOIHXZ
HMQRLUXE
HIVETDEP
DQJCTXNE
SXDOHCYG
TFYKEFJW
TJGXULLS
PMEJGSEF
UYAHBHKS
WALAUWUJ
DQXLTFVG
NVHTNPNA
ILITJIOS
NNFUIMPX
BCUYEIFL
VJWISWVQ
HZNPZZJF
HIJPMRJI
FCXYRPSA
WVOKEXQB
GHYDZKBM

output:

16

result:

ok single line: '16'

Test #18:

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

input:

5 5
LAXXW
ODLAX
XXODX
XXXLA
XXXOD

output:

9

result:

ok single line: '9'

Test #19:

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

input:

5 5
XXXOD
XXXLA
XXODX
ODLAX
LAXXW

output:

9

result:

ok single line: '9'

Test #20:

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

input:

5 5
DOXXX
ALXXX
XDOXX
XALDO
WXXAL

output:

9

result:

ok single line: '9'

Test #21:

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

input:

9 9
XXXODOXXX
XXXLALXXX
XXODXDOXX
ODLAXALDO
LAXXWXXAL
ODLAXALDO
XXODXDOXX
XXXLALXXX
XXXODOXXX

output:

9

result:

ok single line: '9'

Test #22:

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

input:

1 1
W

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 162ms
memory: 7428kb

input:

176 472
KUMYIMXYCXUKCQXPDEOURBXYMTQVXOCYNZYCPKNAYWZMKMKBDYCCLJCWHRWKFAVYRDDQBNONSIQEKWJVUUGICMHFXTRUGLVHELGGSSFMEWXMWKUVMJHBSECGUFVXPKHJGDLNCYWPAAAOAVNKUXXKMLXJSLTJUAJJWVZMJCKTLDRELSUACYKBNRFFZMJODJQQYRTAFUJVENRLBFCQHKCSDBYSMYOYBUAXNDYCSSFYRGTLSMDOEVOWPXPBFBAQWFWEIGOEPUQTGTXTCLOCTUXKEWKFRKVSEPVIMFUA...

output:

5

result:

ok single line: '5'

Test #24:

score: 0
Accepted
time: 278ms
memory: 7776kb

input:

398 244
QUHZAOKHAAFETIKDGMDIOXCZTCNQGQOVKSVMGHWDBJJPZCGFVZOEVWEZQTGOTYHARAKLXBCBTONLOHBPSULLPTZPGLAFMIMFQWTWXZHDJVBEJVQRLCRDTWWDLHCLPQBFWFHOJAMSUHVQIUOKADYJXWCLPVJMULBAHOCXCKLTCIHZRANLLUPPENLIIVVDQSAQIJQPFMWQZEEKELEZTHOPIKOTUJOWPWSFXBENJNPOOWYRCPCGGZCP
GZESAWOKTMDKVDBKPVDXIYXVCWVKSUSUQVUDBMWCWTFFMJR...

output:

6

result:

ok single line: '6'

Test #25:

score: 0
Accepted
time: 109ms
memory: 5728kb

input:

238 211
CORYOZFTAYVYKDDVPCNFQXWJNVKWJRVQNXGCIFBRIUVBKBJDERPYCJLDXLSGKNZKHHJWYEDPODCKAYFIJELZXJVKKWQICLXSUZRTZQNPGRQCOFCPGENFNZBRUZWKBNTMUNZEPAUMMAMWMTJWPBZKMENDJPMFFEEMTKITMKGOZXRYGGCGUTWMQEAMGKZFACJREXAXOLCPMLUFGHRBBDH
HXRBZJEGCZKYRNJXNUIVJWROYDAPATLOJNJDPYYLHZCGBQDTGAPWIVNGIUZDLSOTWKBLWJELJWIFORGV...

output:

5

result:

ok single line: '5'

Test #26:

score: 0
Accepted
time: 7ms
memory: 4144kb

input:

293 43
HJXILPOWPUYLDYHSQHPDKCRVUSVROIQPJUJHOVOUDXR
QFUEWEYZLSXJKPUNXGDUCVPGIZJUAXJUMIOAFIBSZJT
BJFTQUWPOTLSPPRRMGQPRQYZDPSSORDIBYIKKRMQHUP
BXCPCTEDPRPYZRNUQYLMKHNVCAGVAOPIGBKDWGJIIKV
NQUYAFZEZSTUGYOVRYIISVGVKEVXDKBLTYBHDZNZTRQ
VQHJKXGJZYNDBCNTYRPMOHOWVZBJXLDXXVKYOZQUVLU
KJVRYGHWMJEYQVGHTNJQJWKOLFRFZ...

output:

6

result:

ok single line: '6'

Test #27:

score: 0
Accepted
time: 19ms
memory: 4500kb

input:

445 58
KGVWGWIMIGQVKDWAQXZCYKSEEXIXXBWHGPAJWXKCMXNTRRLEICEPLZJHQX
TMPIZUDRGKATXPLULHFFTIDEHAWNWGHYCOTRIWGJIUDOAZUVBESNEQMGQM
GEDWKZHNFVTRPPGGPYUJCISCENNROWSRBTWROXTEDOGGFHRTQCCDIITWCQ
XPHWSDWZHEZBCIXQREGTYCAJLGBUQADEQMPHRYURLYTMATMRGYKSYTHMKY
YWMMNBDNIIAUOUWEWLMNQYQRCREDBOGXDEXOAEMPCZBQEKCTDYVKWOGFO...

output:

6

result:

ok single line: '6'

Test #28:

score: 0
Accepted
time: 58ms
memory: 5664kb

input:

544 95
ZFVLAMXMQPASGTJZSABPYDSOQDVIXDUWJRJUAQKEBHCNHFZNIOTGZXUQIJHEHLICCEENVBZEJKBQBZFOLRKSJFZELDQEWUJ
XZYESFYFLDFSBPAWVOPWEUOPLKZYFOFLWKWHHMVLGSSCPYEHUBOGRWRDXQLQLVGMOAALAIRCBXWUHKMEENNHVHMAZEDEECQ
ODJUZXZOGXVSSSKWTCTJNVKZYDRWPBWFFAJVESWDEOQLOYAYFXNCDCMCFCOTHRWANPVSKCGAOFFCZCALAOVBHBOPWYDEJVY
DKOKG...

output:

5

result:

ok single line: '5'

Test #29:

score: 0
Accepted
time: 42ms
memory: 5900kb

input:

61 950
ESBJPSCSQAEXMVGEVQUFMVAFHVXTPYQFWNJNLBZBAJXRNWIGQUUBBZHJKVFNRJHRVOLFGXNCXOPUZAXQZDYPHQICOGACPJUBLZJININNZPNNVCIAIZRWGKDZXOYAGLWQNXSRKHMAKJPAHNKIOHYGGOISXGSIFQBIJKWXDUDVLQSKGZUZJSXFYSJTSFEDIOQITYMFIPMCTJLHDFYFLVHGLLNCFNGDNLSINXSUEBAJSRRZEOACSTSOVPQJUCYGKYNRAAQGMNTZXIXLMAANUXXJGSPIPQCDROHLSXRDO...

output:

6

result:

ok single line: '6'

Test #30:

score: 0
Accepted
time: 163ms
memory: 6188kb

input:

283 234
ADHGGMRRPRGHQBLDXQDQBGUSXXFLPDQCDEBUSHAPDXRTSRCUKYTQYIPQMKFNPRTIJWFPSJPKPXDFKIGBBAZGPKLANSVTHLDOJNJNWGCLRTKAAIRYGPCNZZPTYUSYIQZZHEDOMHMANKKPCIPACNCMNRAHMAIBZKVPWEILETCCVMKUNFDTHGBHIKBMFDWTFKMYJWKMBSATOHQKVRHEGNCPQRSEBTEHIVZQEDSVOZMTUT
CJWXZVIVIYZGENJMMXBZSGYHMYFDJBZKNJUVJIIDOTRCOFJYLXGHKOAIP...

output:

5

result:

ok single line: '5'

Test #31:

score: 0
Accepted
time: 3ms
memory: 3740kb

input:

46 122
WPQFCTULEZOUZQTUOQBFGBMGCVQCXUCAZHICDJYELAOQCHUWEIZCPBDBSQGGFXYINHOLZZJBOVDZQWHFCSXSIASTLRMJOWICVDLECOZBZGSNKDCSZPGGHJDMTK
CEFHGGTJOHWBLZHOMUGGRRIUBVOPPGCFNWOFCRAANAYUSJWGKQMEICCRBOHDNYXXDQGQBFJVSTIYXTRZBTEZUGTDDBPRXRABYPGHYTPNUSCXWWNKKIGMWHQFUI
TPEKCTRPXJEDFPDYLAGRFDHZDMOKXLYEBELAMGOHDJJGRQV...

output:

5

result:

ok single line: '5'

Test #32:

score: 0
Accepted
time: 30ms
memory: 5516kb

input:

46 1003
LFUCKMVFUPVHECFGASOYVWPPRYFRDQINNSGXSAJOTEXPQKXTBGYEQWKRGEWRAIBRKIWRVGYYNIAZRWGXAWSIHFNSLPGYELNFATKTOLFUQIDKMZTZUCIYHZIKKNZQUCIIWKZFMMWZMGPQUYBWTRBVUBYJWNMJXKBJIZNYFZCIETXBVUFCRUVKUBSNMTLZSIUPDYNMHRNFLINKOIBBMFEETHXRMSMQJZCFSMGDZCBNIRHUOKNUPQTFRLJBGJEMIPKLNOFMJWUJWUBAAMUZGXZLHPJKKBATXROMKGHY...

output:

6

result:

ok single line: '6'

Test #33:

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

input:

5 5
WALDO
ALODW
LODWA
ODWAL
DWALO

output:

5

result:

ok single line: '5'

Test #34:

score: 0
Accepted
time: 132ms
memory: 8084kb

input:

316 316
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXDXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXDXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXLXXXDXXX...

output:

80264

result:

ok single line: '80264'

Test #35:

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

input:

5 5
XXXXX
XXWXX
XALDX
XXOXX
XXXXX

output:

9

result:

ok single line: '9'

Test #36:

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

input:

5 5
XXXXX
XWXAX
XXLXX
XDXOX
XXXXX

output:

9

result:

ok single line: '9'

Test #37:

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

input:

49 49
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

25

result:

ok single line: '25'