Submission #1113671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113671		vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	19 / 100	12 ms	5232 KiB

mushrooms

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

#define i128 __int128
#define ll long long
#define ff first
#define ss second
#define pll pair<ll, ll>
#define pb push_back
#define elif else if

#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const ll MOD = 1e9+7;
const ll base = 1e18;
const ll maxn = 5e5+5;

ll p[maxn];

int main(){
    fast_io;
    ll r,c,d,k;
    cin>>r>>c>>d>>k;
    vector<vector<char>> a(r, vector<char> (c));
    for (int i=0;i<c;i++){
        cin>>a[0][i];
        //cout<<a[0][i]<<endl;
        if (a[0][i]=='S'){
            //range 
            ll start = max(0ll, i - d); 
            ll end = min(c-1,i + d);
            p[start]=p[start]+1;
            p[end+1]=p[end+1]-1;
            //cout<<start<<" "<<end<<endl;
            //the range of the boundary is 0->c-1

        }
    }
    for (int i=1;i<c;i++){
        p[i]=p[i]+p[i-1];
    }
    ll ans=0;
    for (int i=0;i<c;i++){
        if (a[0][i]=='M'&&p[i]>=k){
            ans++;
        }
        //cout<<p[i]<<endl;
    }
    cout<<ans<<endl;
}

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