Submission #925577

#TimeUsernameProblemLanguageResultExecution timeMemory
925577vjudge1Collecting Mushrooms (NOI18_collectmushrooms)C++17
100 / 100
26 ms20056 KiB
//Bismillahir-Rahmanir-Rahim #include <bits/stdc++.h> //#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops") //#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2") #define pb push_back #define pii pair <int, int> #define pll pair <long long, long long> #define pld pair <long double, long double> #define ll long long #define ld long double #define x first #define y second #define all(v) v.begin(),v.end() #define sz(s) (int)s.size() #define skip continue #define bpop(x) (ll)__builtin_popcountll(x) using namespace std; const int N = 5e5 + 7; const int M = 1e3 + 7; const int maxA = 2e6 + 7; const int inf = 1e9 + 7; const ll INF = 2e18 + 7; const int MOD = 1e9 + 7; const ld eps = 1e-9; pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#define int long long int n, m, k, d; void solve() { cin >> n >> m >> d >> k; char a[n + 7][m + 7]; int pre[n + 7][m + 7]; memset(a, 0, sizeof a); memset(pre, 0, sizeof pre); for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { cin >> a[i][j]; if (a[i][j] == 'S') { int x1 = max(1, i - d), y1 = max(1, j - d); int x2 = min(n, i + d), y2 = min(m, j + d); pre[x1][y1]++, pre[x1][y2 + 1]--, pre[x2 + 1][y1]--, pre[x2 + 1][y2 + 1]++; } } } for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++)pre[i][j] += pre[i][j - 1]; } for (int j = 1;j <= m;j++) { for (int i = 1;i <= n;i++)pre[i][j] += pre[i - 1][j]; } int ans = 0; for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { if (a[i][j] == 'M')ans += pre[i][j] >= k; } } cout << ans; } signed main() { //srand(time(NULL)); ios_base::sync_with_stdio(0); cout.tie(0); //freopen("tests.in", "r", stdin); //freopen("milkorder.out", "w", stdout); int test = 1; //cin >> test; for (int t = 1;t <= test;t++) { //cout << "Case " << 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...