#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll r,c,d,k;
cin >> r >> c >> d >> k;
vector <string> arr(r);
vector <vector<ll>> count(r,vector<ll>(c,0));
vector <vector<ll>> hori(r,vector<ll>(c,0));
for (int z=0;z<r;z++){
cin >> arr[z];
}
for (ll z=0;z<r;z++){
for (ll x=0;x<c;x++){
if (arr[z][x] == 'S'){
hori[max(z-d,ll(0))][max(x-d,ll(0))]++;
if (z+d+1 < r)hori[z+d+1][max(x-d,ll(0))]--;
if (x+d+1 < c)hori[max(z-d,ll(0))][x+d+1]--;
if (x+d+1 < c && z+d+1 < r)hori[z+d+1][x+d+1]++;
}
}
}
for (int z=0;z<r;z++){
ll t = 0;
for (int x=0;x<c;x++){
if (hori[z][x] != 0 && z != r-1){
hori[z+1][x] += hori[z][x];
}
t += hori[z][x];
count[z][x] = t;
}
}
ll ans = 0;
for (int z=0;z<r;z++){
for (int x=0;x<c;x++){
if (arr[z][x] == 'M' && count[z][x] >= k){
ans++;
}
}
}
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3832 KB |
Output is correct |
2 |
Correct |
6 ms |
3960 KB |
Output is correct |
3 |
Correct |
7 ms |
4732 KB |
Output is correct |
4 |
Correct |
6 ms |
3960 KB |
Output is correct |
5 |
Correct |
7 ms |
4216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
12592 KB |
Output is correct |
2 |
Correct |
17 ms |
12588 KB |
Output is correct |
3 |
Correct |
18 ms |
12588 KB |
Output is correct |
4 |
Correct |
27 ms |
12592 KB |
Output is correct |
5 |
Correct |
19 ms |
12588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
504 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
3832 KB |
Output is correct |
17 |
Correct |
6 ms |
3960 KB |
Output is correct |
18 |
Correct |
7 ms |
4732 KB |
Output is correct |
19 |
Correct |
6 ms |
3960 KB |
Output is correct |
20 |
Correct |
7 ms |
4216 KB |
Output is correct |
21 |
Correct |
19 ms |
12592 KB |
Output is correct |
22 |
Correct |
17 ms |
12588 KB |
Output is correct |
23 |
Correct |
18 ms |
12588 KB |
Output is correct |
24 |
Correct |
27 ms |
12592 KB |
Output is correct |
25 |
Correct |
19 ms |
12588 KB |
Output is correct |
26 |
Correct |
21 ms |
12024 KB |
Output is correct |
27 |
Correct |
15 ms |
9208 KB |
Output is correct |
28 |
Correct |
16 ms |
9080 KB |
Output is correct |
29 |
Correct |
15 ms |
9208 KB |
Output is correct |
30 |
Correct |
19 ms |
10712 KB |
Output is correct |