This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |