Submission #1006049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006049		devariaota	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	13 ms	17520 KiB

mushrooms

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'

template <typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>; 

const ll MOD = 1e9 + 7;
const ll INF = 1e18;

ll n, m, d, s, a[300005], b[300005];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t = 1;
    //cin >> t;
    
    while(t--){
        cin >> n >> m >> d >> s;
        
        vector<vector<char>> grid(n + 2, vector<char>(m + 2));
        vector<vector<ll>> pref(n + 2, vector<ll>(m + 2));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> grid[i][j];
                pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (grid[i][j] == 'S');
                //cout << pref[i][j] << " ";
            }
            //cout << endl;
        }
        
        ll ans = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(grid[i][j] == 'M'){
                    ll d1 = min(d, n - i), d2 = min(d, m - j), D1 = min(d + 1, (ll)i), D2 = min(d + 1, (ll)j);
                    ll cnt = pref[i + d1][j + d2] - pref[i + d1][j - D2] - pref[i - D1][j + d2] + pref[i - D1][j - D2];
                    if(cnt >= s) ans++;
                }
            }
        }
        
        cout << ans << endl;
    }
        
    return 0;
}

/*
*/

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21