제출 #1271536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271536		yeuler	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	38 / 100	25 ms	5704 KiB

mushrooms

#include <bits/stdc++.h>
#define ll long long
#define KAGAMINE ios_base::sync_with_stdio(false);
#define LEN cin.tie(NULL);
#define slv solve();
#define slve int tc = 1; cin >> tc; while(tc--){solve();}
#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;

void sub5(){
    vector<int> kor;
    for (int i = 0; i < spr.size(); i++){
        kor.pb(spr[i].se);
    }

    sort(all(kor));

    // for (auto x : kor) cout << x << " ";
    // cout << "\n";

    int ans = 0;
    for (int i = 0; i < mus.size(); i++){
        int rn = mus[i].se;
        auto lb = lower_bound(all(kor),rn-d),
        ub = upper_bound(all(kor), rn+d);

        int cnt = ub-lb;

        // cout << ka << " " << ki << "\n";
        if (cnt >= k) ans++;
    }

    cout << ans;
}

void sub3(){
    int ans = 0;
    for (auto [rm, cm] : mus){
        int cnt = 0;
        for (auto [rs, cs] : spr){
            if (abs(rm-rs) <= d && abs(cm-cs) <= d){
                cnt++;
            }
        }
        if (cnt >= k) ans++;
    }

    cout << ans;
}

void fin(){
    vector<int> kor;
    for (int i = 0; i < spr.size(); i++){
        kor.pb(max(spr[i].se,spr[i].fi));
    }

    sort(all(kor));

    // for (auto x : kor) cout << x << " ";
    // cout << "\n";

    int ans = 0;
    for (int i = 0; i < mus.size(); i++){
        int rn = min(mus[i].fi,mus[i].se);
        auto lb = lower_bound(all(kor),rn-d),
        ub = upper_bound(all(kor), rn+d);

        int cnt = ub-lb;

        // cout << ka << " " << ki << "\n";
        if (cnt >= 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});
        }
    }

    if (d == max(r,c) && k == 1){ // subtsk 1
        cout << mus.size();
        return 0;
    }

    if (d == max(r,c)){ // subtsk 2
        if (spr.size() >= k){
            cout << mus.size();
        }
        else {
            cout << 0;
        }
        return 0;
    }

    if (r == 1){
        sub5();
        return 0;
    }

    fin();

    // sub3();

    return 0;
}

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