QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426954 | #4195. Looking for Waldo | rania__# | WA | 0ms | 3676kb | C++20 | 3.0kb | 2024-06-01 02:48:23 | 2024-06-01 02:48:23 |
Judging History
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'