Submission #394318

#TimeUsernameProblemLanguageResultExecution timeMemory
394318ZenWoRCollecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
22 ms14696 KiB
#include <iostream> #include <vector> #include <map> #include <set> #include <algorithm> #define ll long long #define ar array<int> #define pb(x) push_back(x) #define all(x) x.begin(),x.end() using namespace std; //https://oj.uz/problem/view/NOI18_collectmushrooms vector<pair<int,int>> coords; int R,C,D,K; void solve() { cin>>R>>C>>D>>K; vector<vector<int>> t(R+3,vector<int>(C+3)); vector<vector<char>> a(R+3,vector<char>(C+3)); for(int i=1;i<=R;i++) { for(int j=1;j<=C;j++) { cin>>a[i][j]; if(a[i][j]=='S') coords.push_back({i,j}); } } if(!coords.size()) { cout<<0<<endl; return; } for(auto& e: coords) { int x=e.first,y=e.second; int x1=x-D,y1=y-D; int x2=x+D,y2=y+D; x1=max(x1,1); x2=min(x2,R); y1=max(y1,1); y2=min(y2,C); // cout<<"("<<x<<","<<y<<"): "<<x1<<" "<<y1<<"; "<<x2<<" "<<y2<<endl; t[x1][y1]++; t[x2+1][y2+1]++; t[x1][y2+1]--; t[x2+1][y1]--; } ll ans=0; for(int i=2;i<=R;i++) { for(int j=1;j<=C;j++) { t[i][j]+=t[i-1][j]; } } for(int i=1;i<=R;i++) { for(int j=2;j<=C;j++) { t[i][j]+=t[i][j-1]; } } for(int i=1;i<=R;i++) { for(int j=1;j<=C;j++) { // cout<<t[i][j]<<" "; if(a[i][j]=='M' and t[i][j]>=K) ans++; } // cout<<endl; } cout<<ans<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; //cin>>T; while(T--) solve(); 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...