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;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
const ll INF = 1e9;
const ll MOD = 998244353;
const ll MAXN = 3e5 + 5;
const ll LOG = 30;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'
#define lc (pos+1)
#define rc (pos+2*(mid-l+1))
#define mid ((l+r)/2)
ll n, m, d, s;
vector <string> a;
vector <vll> pf;
void solve(){
cin >> n >> m >> d >> s;
pf.resize(n+5);
for(ll i = 0; i < n+5; i++){
pf[i].resize(m+5);
}
a.resize(n+5);
for(ll i = 1; i <= n; i++){
string c; cin >> c;
a[i] = '.' + c;
for(ll j = 1; j <= m; j++){
if(a[i][j] == 'S'){
ll ai = max((ll)1, i-d), aj = max((ll)1, j-d), bi = min(n+1, i+d+1), bj = min(m+1, j+d+1);
pf[ai][aj]++, pf[bi][bj]++;
pf[ai][bj]--, pf[bi][aj]--;
}
}
}
ll ans = 0;
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
pf[i][j] += pf[i-1][j] + pf[i][j-1] - pf[i-1][j-1];
// cout << pf[i][j] << " ";
if(a[i][j] == 'M'){
ans += pf[i][j] >= s;
}
}
// cout << endl;
}
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// ll t; cin >> t;
// while(t--){
solve();
// }
}
# | 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... |