제출 #1015522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015522		ag_1204	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	14 ms	17632 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 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;
}

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