Submission #1127903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127903		Dreamy_lovesper	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	58 ms	66812 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

#define LIFESUCKS                 \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define ll long long
#define pll pair<ll, ll>
#define mll map<ll, ll>
#define vll vector<ll>
#define pb push_back
#define fi first
#define se second
#define all(c) c.begin(), c.end()
#define debug cout << "I Love You\n";
#define Bitc(x, j) ((x >> j) & 1)
#define fu(i, a, b) for (ll i = a; i <= b; i++)
#define fd(i, b, a) for (ll i = b; i >= a; i--)

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 31);
const ll lnf = (1ll << 60);

template <class X, class Y>
bool minimize(X &x, const Y &y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, const Y &y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

#define mxn 1'000'007
ll n, m, d, k;

void lovesper(const ll TestCase) {
    cin >> n >> m >> d >> k;
    vector<vll> g( n +7, vll ( m + 7, 0));
    vector<vll> pref( n +7, vll ( m + 7, 0));
    fu ( i, 1, n ) fu ( j, 1, m ) {
        char x; cin >> x;
        // cout << x << ' ' << " \n"[j == m];
        if ( x == 'M' ) g[i][j] = -1;
        else g[i][j] = ( x == 'S');
        pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + ( x == 'S' );
    }

    ll sad = 0;
    fu ( i, 1, n ) fu ( j, 1, m ) {
        if ( g[i][j] != -1 ) continue;
        ll sum = pref[min(n, i + d)][min(m, j + d)] - pref[min(n, i + d)][max(0ll, j - d - 1)] - pref[max(0ll, i - d - 1)][min(m, j + d)] + pref[max(0ll, i - d - 1)][max(0ll, j - d - 1)];
        // cerr << i << ' ' << j << "  " << sum << '\n';
        if ( sum >= k) sad += 1;
    }
    cout << sad;
}

signed main() {
    LIFESUCKS
    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    ll test = 1;
    //    cin >> test;
    for (int i = 1; i <= test; i++) {
        lovesper(i);
        if (i < test) cout << '\n';
    }
    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