Submission #628579

#	Time	Username	Problem	Language	Result	Execution time	Memory
628579		elesis	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	26 ms	21940 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define int long long 
#define pii pair<int,int> 
#define ff first
#define ss second
const int inf=1e11+7;
const int N=107;
const int mod =1000000007;
vector <int> adj[N];
void solve()
{
    int r,c,d,k;
    cin>>r>>c>>d>>k;
    char grid[r+1][c+1];
    vector <pii> cord;
    vector <vector <int>> pref(r+1,vector <int>(c+1,0));
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            cin>>grid[i][j];
            if(grid[i][j]=='M')
            {
                cord.push_back({i,j});
            }
        }
    }
    for(int i=1;i<=r;i++)
    {
        for(int j=1;j<=c;j++)
        {
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
            if(grid[i][j]=='S')
            {
                pref[i][j]++;
            }
        }
    }
    int ans=0;
    int x1,x2,y1,y2;
    for(auto it:cord)
    {
        x1=max(1LL,it.ff-d);
        y1=max(1LL,it.ss-d);
        x2=min(r,it.ff+d);
        y2=min(c,it.ss+d);
        int spr=pref[x2][y2]-pref[x2][y1-1]-pref[x1-1][y2]+pref[x1-1][y1-1];
        if(spr>=k)
        {
            ans++;
        }
    }
    cout << ans << '\n';
}
signed main()
{
    fast
    clock_t start, end;
    start = clock();
    solve();
    end = clock();
    double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
    //cout << "time taken" << " " << time_taken << "\n";
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:64:12: warning: unused variable 'time_taken' [-Wunused-variable]
   64 |     double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
      |            ^~~~~~~~~~

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