Submission #933092

#	Time	Username	Problem	Language	Result	Execution time	Memory
933092		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	21 ms	31796 KiB

mushrooms

#include <bits/stdc++.h>
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fi first
#define se second
#define pb push_back
#define task "hetcuu"
using namespace std;
using ll = long long;
using ld = long double;
const int maxN = 5e5 + 10;
int r,c,d,k;
vector <int> a[maxN];
vector <int> b[maxN];
void update(int i,int j ,int x){
    if(i > r || j > c) return ;
    i = max(i,1);
    j = max(j,1);
    a[i][j] += x;
}
void init(){
    cin >> r >> c >> d >> k;
    for(int i = 0;i <= r;++i){
        a[i].resize(c + 1);
        b[i].resize(c + 1);
    }
    for(int i = 1;i <= r;++i){
        for(int j = 1;j <= c;++j){
            char tem; cin >> tem;
            if(tem == '.') continue;
            else if(tem == 'M'){
                b[i][j] = 1;
            }
            else{
                update(i - d,j -d,1);
                update(i + d + 1,j - d,-1);
                update(i - d,j + d + 1,-1);
                update(i + d + 1,j + d + 1,1);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= r;++i){
        for(int j = 1;j <= c;++j){
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            if(b[i][j] == 1){
                if(a[i][j] >= k){
                    ans++;
                }
            }
        }
    }
    cout << ans;
}
int main(){
    faster
    init();
}

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