Submission #1307829

#TimeUsernameProblemLanguageResultExecution timeMemory
1307829athenaCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
21 ms19896 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long int

int32_t main()
{
   std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 int n,m,d,k;
 cin>>n>>m>>d>>k;
char grid[n][m];
vector<pair<int,int>>mus;
for(int i=0;i<n;i++)
{
  for(int j=0;j<m;j++){
    cin>>grid[i][j];
    if(grid[i][j]=='M')
      mus.push_back({i,j});
  }
}
vector<vector<int>>p(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++)
{
  for(int j=1;j<=m;j++)
  {
    int s=0;
    if(grid[i-1][j-1]=='S')
    s=1;
  p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+s;
  }
}int ans=0;
for(auto [i,j]:mus)
{
  int r1=max(i-d,0LL);
  int c1=max(j-d,0LL);
  int r2=min(i+d,n-1);
  int c2=min(j+d,m-1);
  r1++;r2++;c2++;c1++;
  int a=p[r2][c2]-p[r1-1][c2]-p[r2][c1-1]+p[r1-1][c1-1];
  if(a>=k)
  ans++;
}
cout<<ans<<endl;
  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...