Submission #1161330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161330		the_ZHER	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	17 ms	16856 KiB

mushrooms

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e18;
const int N=5e5+100;
const int N1=5e5;
const int N2=1e6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int x,w;
};
struct edge1{
    int x,g,d;
};
signed main(){
boost;
    int n,m,d,k;
    cin>>n>>m>>d>>k;
    vector<char>a[n+4];
    vector<int>b[n+4];
    vector<pair<int,int> >v;
    for(int i=1;i<=n;i++){
        b[i].push_back(0);
        a[i].push_back('.');
        for(int j=0;j<m;j++){
            char x;
            cin>>x;
            if(x=='S'){
                v.push_back({i,j+1});
            }
            a[i].push_back(x);
            b[i].push_back(0);
        }
        b[i].push_back(0);
    }
    b[0].push_back(0);
    for(int i=1;i<=m;i++){
        b[0].push_back(0);
    }
    b[0].push_back(0);
    for(int i=0;i<v.size();i++){
        int x=max(v[i].first-d,1ll),y=max(v[i].second-d,1ll);
        int x1=min(v[i].first+d,n),y1=min(v[i].second+d,m);
        b[x][y]++;
        if(y1+1<=m){
        b[x][y1+1]--;
        }
        if(x1+1<=n){
        b[x1+1][y]--;
        if(y1+1<=m){
         b[x1+1][y1+1]++;
         }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int cnt=0;
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='M'&&b[i][j]>=k){
                ans++;
            }
        }
    }
    cout<<ans;
}  

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