Submission #205756

#	Time	Username	Problem	Language	Result	Execution time	Memory
205756		Nnandi	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	28 ms	8940 KiB

mushrooms

#include <bits/stdc++.h>
using namespace std;

const int maxn = 500005;
int r, c, d, k;

vector<pair<int,int> > mush;
vector<vector<int> > sums;

int get(int x, int y) {
    x = min(x,r);
    x = max(x,0);
    y = min(y,c);
    y = max(y,0);
    return sums[x][y];
}

bool water_sat(int x, int y) {
    int all = get(x+d,y+d) - get(x-d-1,y+d) - get(x+d,y-d-1) + get(x-d-1,y-d-1);
    int fr = (all >= k) ? 1 : 0;
    return fr;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>r>>c>>d>>k;
    sums.resize(r+1);
    for(int i=0;i<=r;i++) {
        sums[i].resize(c+1);
    }

    for(int i=1;i<=r;i++) {
        for(int j=1;j<=c;j++) {
            char c;
            cin>>c;
            sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1];
            if(c == 'S') {
                sums[i][j]++;
            }
            else if(c == 'M') {
                mush.push_back(make_pair(i,j));
            }
        }
    }
    int res = 0;
    for(auto d:mush) {
        res += water_sat(d.first,d.second);
    }
    cout<<res<<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