Submission #1174155

#TimeUsernameProblemLanguageResultExecution timeMemory
1174155CiprianCollecting Mushrooms (NOI18_collectmushrooms)C++20
60 / 100
159 ms16552 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int d1[4]={0,0,1,-1}; int d2[4]={1,-1,0,0}; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,m,d,k; cin>>n>>m>>d>>k; map<pair<int,int>, int>wet; vector<pair<int,int>>sprinkler, mush; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ char x; cin>>x; if(x=='S')sprinkler.push_back({i,j}); if(x=='M')mush.push_back({i,j}); } }if(n==1){ vector<pair<int,int>>intervals; for(auto e:sprinkler){ intervals.push_back({max(e.first-d, 1LL), min(e.second+d, m)}); }sort(intervals.begin(), intervals.end()); int cnt=0; vector<int>p(m+2), pref(m+2); for(auto e: intervals){ p[e.first]++; p[e.second+1]--; }for(int i=1; i<=m; i++){ pref[i]=pref[i-1]+p[i]; }for(auto e: mush){ if(pref[e.second]>=k)cnt++; }cout<<cnt<<endl; }else { for(auto e: mush){ for(auto f: sprinkler){ if(max(abs(e.first-f.first), abs(e.second-f.second))<=d){ wet[e]++; } } } int cnt=0; for(auto e: mush){ //cout<<wet[e.first][e.second]<<endl; if(wet[e]>=k)cnt++; }cout<<cnt<<endl; } return 0; }
#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...