제출 #1206359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206359		loom	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	16 ms	16560 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

inline void solve(){
   int n, m, d, k;
   cin>>n>>m>>d>>k;

   int pre[n+1][m+1];
   for(int i=0; i<n; i++) pre[i][0] = 0;
   for(int i=0; i<m; i++) pre[0][i] = 0;

   vector<pair<int,int>> v;
   for(int i=1; i<=n; i++){
      for(int j=1; j<=m; j++){
         char c;
         cin>>c;
         pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (c == 'S');
         if(c == 'M') v.push_back({i, j});
      }
   }

   int ans = 0;
   for(auto [i, j] : v){
      int a = max(i-d, 1ll), b = max(j-d, 1ll), x = min(i+d, n), y = min(j+d, m);
      ans += pre[x][y] - pre[x][b-1] - pre[a-1][y] + pre[a-1][b-1] >= k;
   }

   cout<<ans;
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   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