Submission #7558632


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],mx,my,X,Y,ans,rans;
string s[1000];
int main(void){
    cin>>h>>w>>n>>m;
    //if(h<2*n||w<2*m){
    //    cout<<"W"<<endl;
    //    return 0;
    //}
    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;
        }
    }
    /*
    for(int i=0;i<X;i++){
        cout<<endl;
        for(int j=0;j<Y;j++){
            cout<<dp[i][j];
        }
    }*/
    for(int i=0;i<X;i++){
        for(int j=0;j<Y;j++){
            if(dp[i][j]==1)mx=Y-m;
            else if(dp[i][j]==0&&mx>0){
                dp[i][j]=1;
                mx--;
            }
        }
    }
    for(int i=0;i<Y;i++){
        for(int j=0;j<X;j++){
            if(dp[j][i]==1)my=X-n;
            else if(dp[j][i]==0&&my>0){
                dp[j][i]=1;
                my--;
            }
        }
    }
    
    
    
    
    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;
    ll xans=0,yans=0;
    if(w>2*m&&h>2*m)ans+=(w-2*m)*(n-ho[0]+ho[1]+1);
    else if(w>2*m){
        for(int i=0;i<X;i++)if(dp[i][m]==1)xans++;
        ans+=(w-2*m)*xans;
    }
    //cout<<ans<<endl;
    if(h>2*n&&w>2*m)ans+=(h-2*n)*(m-ho[2]+ho[3]+1);
    else if(h>2*n){
        for(int i=0;i<Y;i++)if(dp[n][i]==1)yans++;
        ans+=(h-2*n)*yans;
    }
    //cout<<(h-2*n)*(m-ho[2]+ho[3]+1)<<"W"<<endl;
    //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 500
Code Size 2113 Byte
Status
Exec Time 66 ms
Memory 32512 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 500 / 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 32 ms 14976 KB
02.txt 9 ms 13568 KB
03.txt 5 ms 9088 KB
04.txt 40 ms 17024 KB
05.txt 4 ms 7040 KB
06.txt 40 ms 17152 KB
07.txt 3 ms 3200 KB
08.txt 6 ms 13184 KB
09.txt 1 ms 256 KB
10.txt 21 ms 24320 KB
11.txt 3 ms 4992 KB
12.txt 7 ms 5760 KB
13.txt 36 ms 25344 KB
14.txt 1 ms 256 KB
15.txt 8 ms 24960 KB
16.txt 21 ms 8064 KB
17.txt 5 ms 5120 KB
18.txt 8 ms 15104 KB
19.txt 3 ms 896 KB
20.txt 35 ms 19328 KB
21.txt 3 ms 640 KB
22.txt 12 ms 8576 KB
23.txt 66 ms 32512 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB
sample-03.txt 1 ms 256 KB
sample-04.txt 1 ms 256 KB
sample-05.txt 1 ms 256 KB