Submission #1015515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015515		ag_1204	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	0 / 100	17 ms	22516 KiB

mushrooms

#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 tt=1; //cin>>tt;
	while(tt--) {
    	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,c);
    	    y1=max(y1-1,(ll) 0); y2=min(y2,r);
    	    ll count=grid[x2][y2]-grid[x1][y2]-grid[x2][y1]+grid[x1][y1];
    	    if (count>=k) {
    	        ans++;
    	    }
    	}
    	cout<<ans<<endl;
    }
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21