Submission #623448

#TimeUsernameProblemLanguageResultExecution timeMemory
623448hailCollecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
24 ms20900 KiB
#include <bits/stdc++.h> using namespace std; #define vi vector<int> #define vll vector<long long> #define pb push_back using ll= long long; #define fast_io ios::sync_with_stdio(0); cin.tie(0) #define inpint(x) int x; cin>>x #define inpll(x) long long x; cin>>x #define fl(i, n) for(int i=0; i<n; i++) #define fl_1(i, n) for(int i=1; i<=n; i++) #define int long long #define pi pair<int, int> #define mp make_pair #define ld long double void solve() { int r, c, d, k; cin>>r>>c>>d>>k; vector<pi> mushrooms(0); vector<vector<int>> sp_pre(r+1, vector<int>(c+1, 0)); for(int i=1; i<=r; i++) { for(int j=1; j<=c; j++) { char a; cin>>a; sp_pre[i][j] = sp_pre[i-1][j] + sp_pre[i][j-1] - sp_pre[i-1][j-1]; if(a=='M') { mushrooms.pb(mp(i, j)); } else if(a=='S') { sp_pre[i][j]++; } } } int ans{}; for(auto i: mushrooms) { pi tl = mp(max((int)1, i.first-d), max((int)1, i.second-d)); pi br = mp(min(r, i.first+d), min(c, i.second+d)); int nmus = sp_pre[br.first][br.second] - sp_pre[tl.first-1][br.second] - sp_pre[br.first][tl.second-1] + sp_pre[tl.first-1][tl.second-1]; if(nmus>=k) ans++; } cout<<ans<<"\n"; } int32_t main() { fast_io; int t=1; //cin>>t; while(t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...