Submission #534195

#	Time	Username	Problem	Language	Result	Execution time	Memory
534195		kebine	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	1271 ms	94752 KiB

mushrooms

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll MOD=1e9+7;
using namespace std;
ll N,M,P,Q;
map <pair<ll,ll>,char> a;
map <pair<ll,ll>,ll> pref;

int main(){
  cin>>N>>M>>P>>Q;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      cin>>a[{i,j}];
    }
  }
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      if(a[{i,j}]=='S'){
        pref[{i,j}]=pref[{i-1,j}]+pref[{i,j-1}]-pref[{i-1,j-1}]+1;
      }
      else{
        pref[{i,j}]=pref[{i-1,j}]+pref[{i,j-1}]-pref[{i-1,j-1}];
      }
    }
  }
  ll catat=0;
  ll e,f,g,h;
  for(int i=1;i<=N;i++){
    for(int j=1;j<=M;j++){
      if(a[{i,j}]=='M'){
        e=max(1ll,i-P);
        f=min(N,i+P);
        g=max(1ll,j-P);
        h=min(M,j+P);
        ll x=pref[{f,h}]-pref[{f,g-1}]-pref[{e-1,h}]+pref[{e-1,g-1}];
        if(x>=Q){
          catat++;
        }
      }
    }
  }
  cout<<catat<<endl;
}

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