Submission #649581

#	Time	Username	Problem	Language	Result	Execution time	Memory
649581		ZaZo_	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	44 ms	13496 KiB

mushrooms

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mesh !
using namespace std;
const int N = 10 , MOD = 1e9+7 , INF = 1e12;
const double EPS=1e-10, PI=3.141592653589793238462643383279502;
vector<char>cur;

int32_t main()
{
    //freopen("abc.in", "r", stdin);
    //fast;

    /*
    brainzeftstorming
    - law 3mlt BS momken ya5od n^2 momken ygeeb awel 4 subtasks momkeeen
    - el fekra bta3et cses lma kona bn3ml +1 w -1 w n3ml pref sum b3dha -
    - momken n3mel 2d pref sum 3la kol 'S' n3lem el square el heya hta5do b enna n3mel enter b 1 w exit b -1
    - tab ma n3mel 2d pref sum bas 3la 'S' 3shan n3raf fe kam 'S' fe el range lol
    */

    int r , c , d , k;
    cin >> r >> c >> d >> k ;

    char grid[r+1][c+1] ; int pref[r+2][c+2];
    for(int i = 0 ; i <= r+1 ; i ++)  for(int j = 0 ; j <= c+1 ; j ++) pref[i][j]=0;
    for(int i = 1 ; i <= r ; i ++)
      for(int j = 1 ; j <= c ; j ++)
        {
          cin >> grid[i][j];
          if(grid[i][j]=='S') pref[i][j]++;
        }

    //n3mel 2d prefsum 3shan nzbat el ranges
    for(int i = 1 ; i <= r+1 ; i ++)
    {
      for(int j = 1 ; j <= c+1 ; j ++)
      {
        pref[i][j] = pref[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
      }
    }

    //m7tagen n3raf l kol 'M' el square range el heya feeh fe kam S

    int ans=0;
    for(int i = 1 ; i <= r ; i ++)
    {
      for(int j = 1 ; j <= c ; j ++)
      {
        if(grid[i][j]!='M') continue;
        int top = max(1ll , i-d);
        int left = max(1ll , j-d);
        int right = min(c , j+d);
        int bottom = min(r , i+d);
        int cur = pref[bottom][right] - pref[top-1][right] - pref[bottom][left-1] + pref[top-1][left-1];
        ans+=(cur>=k);
      }
    }
    cout<<ans<<endl;
}

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