Submission #1271538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271538		yeuler	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	12 ms	9196 KiB

mushrooms

#include <bits/stdc++.h>
#define ll long long
#define KAGAMINE ios_base::sync_with_stdio(false);
#define LEN cin.tie(NULL);
#define pls cout << "mantap\n";
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define vector2d(x) vector<vector<x>>
#define pii pair<int, int>
#define pl pair<ll, ll>
using namespace std;

int r, c, d, k;
vector<pii> mus, spr;

int addsum(vector2d(int)& pf, int r1, int c1, int r2, int c2){
    int dec1 = 0, dec2 = 0, inc = 0;
    if (r1 > 0) dec1 = pf[r1-1][c2];
    if (c1 > 0) dec2 = pf[r2][c1-1];
    if (r1 > 0 && c1 > 0) inc = pf[r1-1][c1-1];
    return pf[r2][c2] - dec1 - dec2 + inc;
}

void fin(){
    vector2d(int) pf(r, vector<int>(c, 0));
    for (auto [rs, cs] : spr){
        pf[rs][cs] = 1;
    }

    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            if (i > 0) pf[i][j] += pf[i-1][j];
            if (j > 0) pf[i][j] += pf[i][j-1];
            if (i > 0 && j > 0) pf[i][j] -= pf[i-1][j-1];
        }
    }

    int ans = 0;
    for (auto [mr, mc] : mus){
        if (addsum(pf, max(0,mr-d), max(0,mc-d), min(r-1,mr+d), min(c-1,mc+d)) >= k){
            ans++;
        }
    }

    cout << ans;
}

int main(){
    KAGAMINE LEN

    cin >> r >> c >> d >> k;

    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            char tmp; cin >> tmp;
            if (tmp == 'S') spr.pb({i,j});
            if (tmp == 'M') mus.pb({i,j});
        }
    }

    fin();

    // sub3();

    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