Submission #1183739

#TimeUsernameProblemLanguageResultExecution timeMemory
1183739santi3223Collecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
21 ms28416 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define ed "\n"
#define fi first
#define se second
#define pll pair<ll, ll>
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define pb push_back
#define all(aaa) aaa.begin(), aaa.end()

int main(){
	ll n, m, d, k;
	cin >> n >> m >> d >> k;
	vs arr(n);
	ff(i, 0, n){
	    cin >> arr[i];
	}
	vector<vl> psum(n+5, vl(m+5, 0));
	ff(i, 0, n){
	    ff(j, 0, m){
	        if(arr[i][j] == 'S'){
	            ll xiz = max(0LL, j-d), xder = min(m, j+d+1);
	            ll yar = max(0LL, i-d), yab = min(n, i+d+1);
	            psum[yar][xiz]++;
                psum[yab][xder]++;
                psum[yar][xder]--;
                psum[yab][xiz]--;
	        }
	    }
	}
	/*ff(i, 0, n){
	    ff(j, 0, m){
	        cout << psum[i][j] << " ";
	    }
	    cout << ed;
	}
	cout << ed;*/
	ff(i, 0, n){
	    ff(j, 1, m){
	        psum[i][j] += psum[i][j-1];
	    }
	}
	/*ff(i, 0, n){
	    ff(j, 0, m){
	        cout << psum[i][j] << " ";
	    }
	    cout << ed;
	}
	cout << ed;*/
	ff(i, 1, n){
	    ff(j, 0, m){
	        psum[i][j] += psum[i-1][j];
	    }
	}
	/*ff(i, 0, n){
	    ff(j, 0, m){
	        cout << psum[i][j] << " ";
	    }
	    cout << ed;
	}
	cout << ed;*/
	ll c = 0;
	ff(i, 0, n){
	    ff(j, 0, m){
	        if(arr[i][j] == 'M'){
	            if(psum[i][j] >= k){
	                c++;
	            }
	        }
	    }
	}
	cout << c;
	
	
	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...