| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1060410 | Kazoo | Collecting Mushrooms (NOI18_collectmushrooms) | C++17 | 0 ms | 0 KiB |
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 <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxR = 5e5+5;
int r, c, d, k;
string garden[maxR];
bool watered[maxR][maxR];
int main(){
cin >> r >> c >> d >> k;
for(int i = 0; i<r; i++){
cin >> garden[i];
}
vector<vector<int>> kena;
for(int i = 0; i<r; i++){
vector<int> ps;
for(int j = 0; j<c; j++){
ps.push_back(0);
}
kena.push_back(ps);
}
for(int i = 0; i<r; i++){
for(int j = 0; j<c; j++){
if(garden[i][j]=='S')
{
// atas kiri [i-d][j-d]
// bawah kanan [i+d][j+d]
// atas kanan [i-d][j+d]
// bawah kiri [i+d][j-d]
int atas = max(i-d, 0);
int kiri = max(j-d, 0);
kena[atas][kiri]++;
int kanan = -1, bawah = -1;
if(i+d+1<=r-1) bawah = i+d+1;
if(j+d+1<=c-1) kanan = j+d+1;
if(kanan!=-1) kena[atas][kanan]--;
if(bawah!=-1) kena[bawah][kiri]--;
if(kanan!=-1 && bawah!=-1) kena[kanan][bawah]++;
}
}
}
ll ans = 0;
for(int i = 0; i<r; i++){
for(int j = 0; j<c; j++){
if(i!=0) kena[i][j] += kena[i-1][j];
if(j!=0) kena[i][j] += kena[i][j-1];
if(i!=0 && j!=0) kena[i][j] -= kena[i-1][j-1];
if(garden[i][j]=='M' && kena[i][j] >= k) ans++;
}
// cout << endl;
}
cout << ans << endl;
}