Submission #873531

#	Time	Username	Problem	Language	Result	Execution time	Memory
873531		dsyz	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	19 ms	17576 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ios_base::sync_with_stdio(false);cin.tie(0);
  ll R,C,D,K;
  ll sum = 0;
  ll num = 0;
  cin>>R>>C>>D>>K;
  char arr[R + 1][C + 1];
  ll dp[R + 1][C + 1];
  ll ans[R + 1][C + 1];
  //memset(arr,0,sizeof(arr));
  memset(dp,0,sizeof(dp));
  memset(ans,0,sizeof(ans));
  for(ll i = 1;i <= R;i++){
    for(ll j = 1;j <= C;j++){
      cin>>arr[i][j];
    }
  }
  for(ll i = 1;i <= R;i++){
    for(ll j = 1;j <= C;j++){
      if(arr[i][j] == 'S'){
        dp[i][j] = 1;
        //num += 1;
        //dp[i][j] = num;
      }
      //dp[i][j] = num;
    }
  }
  for(ll i = 1;i <= R;i++){
    for(ll j = 0;j <= C;j++){
      ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + dp[i][j];
    }
  }  
  // for(ll i = 1;i <= C;i++){
  //   for(ll j = 1;j <= R;j++){
  //     if(arr[j][i] == 'S'){
  //       num += 1;
  //       //dp[i][j] = num;
  //     }
  //     dp[j][i] = num;
  //   }
  // }  
  for(ll i = 1;i <= R;i++){
    for(ll j = 1;j <= C;j++){
      //cout<<"ARR: "<<arr[i][j]<<" "<<i<<" "<<j<<'\n';
      if(arr[i][j] == 'M'){
        ll a = i - D;
        ll b = j - D;
        ll c = i + D;
        ll d = j + D;
        if(a <= 0){
          a = 1;
        }
        if(b <= 0){
          b = 1;
        }
        if(c > R){
          c = R;
        }
        if(d > C){
          d = C;
        }
        //a = 0,b = 4,c = 2;d = 6(5)
        //cout<<"M: "<<i<<" "<<dp[c][d] - dp[a - 1][d] - dp[c][b - 1] + dp[a - 1][b - 1]<<'\n';
        if(ans[c][d] - ans[a - 1][d] - ans[c][b - 1] + ans[a - 1][b - 1] >= K){
          sum += 1;
        } 
      }
    }
  }
  cout<<sum<<'\n';
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:8:6: warning: unused variable 'num' [-Wunused-variable]
    8 |   ll num = 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