Submission #535545

#	Time	Username	Problem	Language	Result	Execution time	Memory
535545		devariaota	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	31 ms	17480 KiB

mushrooms

/*
    Does he have IGM on CF?
    -neko_nyaa
*/
#include <bits/stdc++.h>
using namespace std;

//define
#define PB push_back
#define MP make_pair
#define pi acos(-1)
#define int long long

//constant
const int mod=1e9+7;
const long long MOD=998244353LL;
const long long inf=(long long)1e18;
 
//typedef
typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef map<string,int> msi;
typedef set<int> SI;
typedef priority_queue<int> pqi;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("haybales.in", "r", stdin);
    //freopen("haybales.out", "w", stdout);
    int r,c,d,k;
    cin >> r >> c >> d >> k;
    char s[r+1][c+1];
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        cin >> s[i][j];
    }
    /*for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        cout << s[i][j];
        cout << '\n';
    }*/
    int pref[r+1][c+1];
    memset(pref,0,sizeof(pref));
    vector<pii> loc;
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            if(s[i][j]=='M')
            {
                loc.push_back({i,j});
            }
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(s[i][j]=='S');
        }
    }
    int ans=0;
    //cout << loc.size() << '\n';
    for(auto &[i,j]:loc)
    {
        int minx=max(1LL,i-d);
        int maxx=min(r,i+d);
        int miny=max(1LL,j-d);
        int maxy=min(c,j+d);
        int total=pref[maxx][maxy]-pref[maxx][miny-1]-pref[minx-1][maxy]+pref[minx-1][miny-1];
        ans+=(total>=k);
    }
    cout << ans << '\n';

    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