Submission #7555796


Source Code Expand

Copy
#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,h,w,ho[]={1000,-1,1000,-1},dp[2000][2000],dp2[2000][2000],mx,my,X,Y,ans,rans;
string s[1000];
int main(void){
    cin>>h>>w>>n>>m;
    for(int i=0;i<n;i++)cin>>s[i];
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            if(s[i][j]=='#'){
                ho[0]=min(ho[0],i);
                ho[2]=min(ho[2],j);
                ho[1]=max(ho[1],i);
                ho[3]=max(ho[3],j);
            }
        }
    }
    if(ho[0]==1000){
        cout<<0<<endl;
        return 0;
    }
    X=min(h,2*n);
    Y=min(w,2*m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'){
                dp[i][j]=1;
                dp[i+X-n][j]=1;
                dp[i][j+Y-m]=1;
                dp[i+X-n][j+Y-m]=1;
                dp2[i][j]=1;
                dp2[i+X-n][j]=1;
                dp2[i][j+Y-m]=1;
                dp2[i+X-n][j+Y-m]=1;
            }
        }
    }
    for(int i=0;i<X;i++){
        mx=0;
        for(int j=0;j<Y;j++){
            //cout<<dp[i][j];
            if(dp[i][j]==1)mx=1;
            if(dp[i][j]==0&&mx==1)dp[i][j]=dp[i][j-1]+1;
        }
        //cout<<endl;
        mx=0;
        for(int j=Y-1;j>=0;j--){
            if(dp[i][j]==1)mx=1;
            else if(dp[i][j]>1&&dp[i][j]<=w-m&&mx==1)dp[i][j]=1;
            else dp[i][j]=0;
        }
    }
    for(int i=0;i<Y;i++){
        mx=0;
        for(int j=0;j<X;j++){
            if(dp[j][i]==1)mx=1;
            if(dp[j][i]==0&&mx==1)dp[j][i]=dp[j-1][i]+1;
        }
        mx=0;
        for(int j=X-1;j>=0;j--){
            if(dp[j][i]==1)mx=1;
            else if(dp[j][i]>1&&dp[j][i]<=h-n&&mx==1)dp[j][i]=1;
        }
    }
    for(int i=0;i<X;i++){
        //cout<<endl;
        for(int j=0;j<Y;j++){
            if(dp[i][j]==1)ans++;
            //cout<<dp[i][j];
        }
    }
    //cout<<ans<<endl;
    if(w>2*m)ans+=(w-2*m)*(n-ho[0]+ho[1]+1);
    //cout<<ans<<endl;
    if(h>2*n)ans+=(h-2*n)*(m-ho[2]+ho[3]+1);
    //cout<<ans<<endl;
    if(h>2*n&&w>2*m)ans+=(h-2*n)*(w-2*m);
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task D - ハンコ
User alorie
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2179 Byte
Status
Exec Time 87 ms
Memory 62720 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
All 0 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, sample-05.txt
Case Name Status Exec Time Memory
01.txt 46 ms 29312 KB
02.txt 13 ms 27904 KB
03.txt 7 ms 19200 KB
04.txt 47 ms 34688 KB
05.txt 6 ms 14976 KB
06.txt 48 ms 32896 KB
07.txt 4 ms 7168 KB
08.txt 8 ms 31104 KB
09.txt 1 ms 256 KB
10.txt 26 ms 50944 KB
11.txt 5 ms 13184 KB
12.txt 8 ms 11520 KB
13.txt 47 ms 51968 KB
14.txt 2 ms 2304 KB
15.txt 12 ms 53504 KB
16.txt 26 ms 18304 KB
17.txt 6 ms 11264 KB
18.txt 10 ms 31104 KB
19.txt 4 ms 4608 KB
20.txt 45 ms 35968 KB
21.txt 3 ms 2688 KB
22.txt 14 ms 15872 KB
23.txt 87 ms 62720 KB
sample-01.txt 2 ms 2304 KB
sample-02.txt 2 ms 2304 KB
sample-03.txt 1 ms 256 KB
sample-04.txt 2 ms 2304 KB
sample-05.txt 2 ms 2304 KB