Submission #1006066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006066		christinelynn	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	26 ms	18012 KiB

mushrooms

#include<bits/stdc++.h>

/* Pragmaaa */
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

/*  Primitive Data   */
#define ll long long
#define db double

/*  Pair Macro */
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define sc second

/* Vector Macro */
#define vi vector<int>
#define vll vector<ll>
#define pb push_back

/*  All Rounder  */
#define all(x) x.begin(),x.end()
#define forn(i,n) for(int (i) = 1; i<= int (n); i++)
#define for0(i,n) for(int (i) = 0; i < int (n); i++)

#define INF 1e9 
#define LLINF 1e18
#define nl '\n'
#define tab '	'

// Hati-hati kalau mau ngeflush tapi endl jadi nya '\n'
#define flushmanual ios_base::sync_with_stdio(false); cin.tie(NULL)

/* Modulo Fuctions */
const ll MOD = 1e9+7;

ll tambah(ll a, ll b){
  return (a+b)%MOD;
}

ll kurang(ll a, ll b){
  return (((a - b) % MOD) + MOD) % MOD;
}

ll mul(ll a, ll b){
  return ((a%MOD) * (b%MOD))%MOD;
}

/* debuggin */
#define debugl cout<<"Here\n"
#define debug(awok) cout<<(awok)<<endl

/* stuff you should look for

  * int overflow, array bounds
  * special cases (n=1?)
  * do smth instead of nothing and stay organized
  * WRITE STUFF DOWN
  * DON'T GET STUCK ON ONE APPROACH (TRY DP INSTEAD OF GREEDY AND VICE VERSA)(DONT FORGET SORTING)
  * TRY ALL STRATEGIES
  * DO NOT READ EDITORIALS BEFORE TRYING REALLY HARD!
  * careful references in recursion
  * careful copying when doing vectors esp in loops and functions
  * careful long long int and mod always OMG
  * careful return types of std such as int(ceil)
  * WATCH OUT GOING OVER MAX thru operations spam mod
  * vectors overflow arrays do NOT
  * cout endl lol
  * lower bound is first greater or equal
  * upper is first greater
  * if TLE play around with compiler
  * use static is helpful!!
  * take note of test stuff that need to be changed before submission
  * careful when u use garbage from abroad
  * careful modeling stuff as num going below 0 above n
  * number theory infinite due to multple of each other
  * careful not finding stuff in dictionaries
  * stupid cout precision and sci notations
  * in sets, rbegin() or --end() for last
  * careful multiset removal just use heapp
  * no segment trees if partial mins are needed, use sparse table
  * in combinatorics log matters esp in that dp, and think v carefully
  * NEVER INPUT DOUBLES
  * fraction class or multiplication tricks?
  * omg dont forget to flush when debugging
  * watch out for bitwise operations order of operations
  * PQ Greater top is smallest and Less top is largest
*/   

using namespace std;



void solve(){
  
  
  
  
    
}

int main(){
  ll r,c,d,s;
  cin >> r >> c >> d >> s;
  
  char arr[r+3][c+3];
  ll pref[r+3][c+3] = {0};
  forn(i,r)forn(j,c){
    cin>> arr[i][j];
    if(arr[i][j] == 'S'){
      pref[max(1LL,i-d)][max(1LL,j-d)]++;
      
      if(i+d+1 <= r && j-d <= c)pref[min(r,i+d+1)][max(1LL,j-d)]--;
      if(i-d <= r && j+d+1 <= c)pref[max(1LL,i-d)][min(c,j+d+1)]--;
      if(i+d+1 <= r && j+d+1 <= c)pref[i+d+1][j+d+1]++;
    }  
  } 
//  forn(i,r){
//    
//    forn(j,c){
//      cout << pref[i][j] << ' ';
//    }cout << nl;
//  }
  
  forn(i,r)forn(j,c){
    if(i == 1 && j == 1)continue;
    
    if(i == 1){
      pref[i][j] += pref[i][j-1];
      continue;
    }
    if(j == 1){
      pref[i][j] += pref[i-1][j];
      continue;
    }
    pref[i][j] += pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
  }
//  forn(i,r){
//    forn(j,c){
//      cout << pref[i][j] << ' ';
//    }cout << nl;
//  }
  ll cnt = 0;
  forn(i,r){
    forn(j,c){
      if(arr[i][j] == 'M' && pref[i][j] >= s)cnt++;
    }
  }
  cout << cnt;
}          

             

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:24:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define forn(i,n) for(int (i) = 1; i<= int (n); i++)
      |                           ^
mushrooms.cpp:109:3: note: in expansion of macro 'forn'
  109 |   forn(i,r)forn(j,c){
      |   ^~~~
mushrooms.cpp:24:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define forn(i,n) for(int (i) = 1; i<= int (n); i++)
      |                           ^
mushrooms.cpp:109:12: note: in expansion of macro 'forn'
  109 |   forn(i,r)forn(j,c){
      |            ^~~~
mushrooms.cpp:24:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define forn(i,n) for(int (i) = 1; i<= int (n); i++)
      |                           ^
mushrooms.cpp:126:3: note: in expansion of macro 'forn'
  126 |   forn(i,r)forn(j,c){
      |   ^~~~
mushrooms.cpp:24:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define forn(i,n) for(int (i) = 1; i<= int (n); i++)
      |                           ^
mushrooms.cpp:126:12: note: in expansion of macro 'forn'
  126 |   forn(i,r)forn(j,c){
      |            ^~~~
mushrooms.cpp:24:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define forn(i,n) for(int (i) = 1; i<= int (n); i++)
      |                           ^
mushrooms.cpp:145:3: note: in expansion of macro 'forn'
  145 |   forn(i,r){
      |   ^~~~
mushrooms.cpp:24:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   24 | #define forn(i,n) for(int (i) = 1; i<= int (n); i++)
      |                           ^
mushrooms.cpp:146:5: note: in expansion of macro 'forn'
  146 |     forn(j,c){
      |     ^~~~

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