제출 #1309483

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309483		tnt	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	16 ms	9408 KiB

mushrooms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back                    
#define ll long long  
//#define sz(v) int(v.size())
#define all(v) v.begin(),v.end()

int mod =  1e9 + 7;
const int N = 2e5,k = 317 + 1;
const ll inf = 3e14;
void solve(){
	int n,m,d,k;
    cin >> n >> m >> d >> k;
    char a[n + 1][m + 1];
    int w[n + 2][m + 2];
    vector <pair <int,int>> v;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            if(a[i][j] == 'S') v.pb({i,j});
        }   
    }
    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= m + 1; j++){
            w[i][j] = 0;
        }
    }
    for(auto [x,y] : v){
        w[max(1,x - d)][max(1,y - d)]++;
        w[min(n,x + d) + 1][max(1,y - d)]--;
        w[max(1,x - d)][min(m,y + d) + 1]--;
        w[min(n,x + d) + 1][min(m,y + d) + 1]++;
    }
    for(int j = 1; j <= m; j++){
        for(int i = 1; i <= n; i++){
            w[i][j] += w[i - 1][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            w[i][j] += w[i][j - 1];
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == 'M' && w[i][j] >= k)ans++;
        }
    }
    cout << ans;     
}
signed main(){
    //freopen("time.in", "r", stdin);
    //freopen("time.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
}                          	

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