Submission #394318

#	Time	Username	Problem	Language	Result	Execution time	Memory
394318		ZenWoR	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	22 ms	14696 KiB

mushrooms

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

#define ll long long
#define ar array<int>
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()

using namespace std;

//https://oj.uz/problem/view/NOI18_collectmushrooms

vector<pair<int,int>> coords;
int R,C,D,K;

void solve() {
  cin>>R>>C>>D>>K;
  vector<vector<int>> t(R+3,vector<int>(C+3));
  vector<vector<char>> a(R+3,vector<char>(C+3));
  for(int i=1;i<=R;i++) {
    for(int j=1;j<=C;j++) {
      cin>>a[i][j];
      if(a[i][j]=='S')
        coords.push_back({i,j});
    }
  }
  if(!coords.size()) {
    cout<<0<<endl;
    return;
  }
  for(auto& e: coords) {
    int x=e.first,y=e.second;
    int x1=x-D,y1=y-D;
    int x2=x+D,y2=y+D;
    x1=max(x1,1);
    x2=min(x2,R);
    y1=max(y1,1);
    y2=min(y2,C);
//    cout<<"("<<x<<","<<y<<"): "<<x1<<" "<<y1<<"; "<<x2<<" "<<y2<<endl;
    t[x1][y1]++;
    t[x2+1][y2+1]++;
    t[x1][y2+1]--;
    t[x2+1][y1]--;
  }
  ll ans=0;
  for(int i=2;i<=R;i++) {
    for(int j=1;j<=C;j++) {
      t[i][j]+=t[i-1][j];
    }
  }
  for(int i=1;i<=R;i++) {
    for(int j=2;j<=C;j++) {
      t[i][j]+=t[i][j-1];
    }
  }
  for(int i=1;i<=R;i++) {
    for(int j=1;j<=C;j++) {
//      cout<<t[i][j]<<" ";
      if(a[i][j]=='M' and t[i][j]>=K)
        ans++;
    }
//    cout<<endl;
  }
  cout<<ans<<endl;
}

signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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