Submission #1015522

#TimeUsernameProblemLanguageResultExecution timeMemory
1015522ag_1204Collecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
14 ms17632 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll r,c,d,k; cin>>r>>c>>d>>k;
    ll grid[r+1][c+1];
    for (ll i=0;i<=r;i++) {
        grid[i][0]=0;
    }
    for (ll i=0;i<=c;i++) {
        grid[0][i]=0;
    }
    vector<pair<ll,ll>> mush;
    for (ll i=1;i<=r;i++) {
        string s; cin>>s;
        for (ll j=1;j<=c;j++) {
            if (s[j-1]=='M') {
                pair<ll,ll> p;
                p.first=i; p.second=j;
                mush.push_back(p);
            }
            grid[i][j]=grid[i-1][j]+grid[i][j-1]-grid[i-1][j-1];
            if (s[j-1]=='S') grid[i][j]++;
        }
    }
    ll ans=0;
    for (auto p:mush) {
        ll x1=p.first-d,x2=p.first+d,y1=p.second-d,y2=p.second+d;
        x1=max(x1-1,(ll) 0); x2=min(x2,r);
        y1=max(y1-1,(ll) 0); y2=min(y2,c);
        ll count=grid[x2][y2]-grid[x1][y2]-grid[x2][y1]+grid[x1][y1];
        if (count>=k) {
            ans++;
        }
    }
    cout<<ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...