Submission #163786

#	Time	Username	Problem	Language	Result	Execution time	Memory
163786		Knps4422	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	60 ms	12876 KiB

mushrooms

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#include<bits/stdc++.h>
#define fr first
#define sc second
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
const int inf = 1e9+7;
const ll linf = 1e18+5;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); //uid<int> u1(5, 10); u1(rnd);
int n , m, d, k;
vec < pii > mushrooms;
int main(){
    fast;
    ll rez = 0;
    cin >> n >> m >> d >> k;
    char ch;
    vec< vec < int >  > tb (n + 2, vec <int> (m + 2) );
    for(int i = 1; i <= n;  i++){
    	for(int j = 1 ; j <= m ; j++){
    		cin >> ch;
    		if(ch == 'M'){
    			mushrooms.pb({i,j});
    		}
    		if(ch == 'S'){
    			//Update table
    			tb[i][j] = 1;
    		}
    	}
    }
    //Compute table
    for(int i = n ; i > 0 ; i--){
    	for(int j = m ; j > 0 ; j--){
    		tb[i][j] += tb[i+1][j] + tb[i][j+1] - tb[i+1][j+1];
    	}
    }
    // Ans Queries
    for(auto mush : mushrooms){
    	int x1 = mush.fr - d , x2 = mush.fr + d + 1 , y1 = mush.sc - d , y2 = mush.sc + d + 1;
    	x1 = max(1,x1);
    	y1 = max(1,y1);
    	x2 = min(n+1,x2);
    	y2 = min(m+1,y2);
    	if(tb[x1][y1] + tb[x2][y2] - tb[x1][y2] - tb[x2][y1] >= k){
    		rez ++;
    	}
    }
    cout << rez;
}

Compilation message (stderr)

mushrooms.cpp:1:0: warning: ignoring #pragma optimization_level  [-Wunknown-pragmas]
 #pragma optimization_level 3

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