Submission #925570

#TimeUsernameProblemLanguageResultExecution timeMemory
925570vjudge1Collecting Mushrooms (NOI18_collectmushrooms)C++17
56 / 100
12 ms6604 KiB
// By ObeliX #include <bits/stdc++.h> #pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #include <unordered_map> #include <cstddef> #include <cassert> #include <bitset> #include <algorithm> #include <iostream> #include <iomanip> #include <cmath> #include <queue> #include <map> #include <set> using namespace std; const long long N = 1e6 + 5; const long long MOD = 1e7 + 7; const long long inf = 1e18; long long n , m , d , k; char c[5001][5001]; int main(){ //freopen( "cinema.in" , "r" , stdin ); //freopen( "cinema.out" , "w" , stdout ); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> d >> k; long long cnt1 = 0 , cnt2 = 0; for ( int i = 1 ; i <= n ; i++ ) { for ( int j = 1 ; j <= m ; j++ ) { cin >> c[i][j]; if ( c[i][j] == 'S' ) { cnt1++; } if ( c[i][j] == 'M' ) { cnt2++; } } } if ( d == max( n , m ) && cnt1 >= k ) { cout << cnt2 ; } else { if ( d == 1 && k == 1 ) { long long ans = 0; for ( int i = 1 ; i <= n ; i++ ) { for ( int j = 1 ; j <= m ; j++ ) { if ( c[i][j] == 'M' ) { if ( c[i][j-1] == 'S' || c[i-1][j] == 'S' || c[i+1][j] == 'S' || c[i][j+1] == 'S' ||c[i+1][j-1] == 'S' ||c[i-1][j+1] == 'S' ||c[i-1][j-1] == 'S' ||c[i+1][j+1] == 'S') { ans++; } } } } cout << ans; } else { if ( n == 1 ) { long long scan[m+5]; for ( int i = 0 ; i <= m ; i++ ) { scan[i] = 0; } for ( int i = 1 ; i <= m ; i++ ) { if ( c[1][i] == 'S' ) { scan[min( m + 1 , i + d + 1 )]--; scan[max( 1ll , i - d )]++; } } long long ans = 0; for ( int i = 1 ; i <= m ; i++ ) { scan[i] += scan[i-1]; if ( c[1][i] == 'M' && scan[i] >= k ) { ans++; } } cout << ans; } else { cout << 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...