Submission #1101274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101274		Roumak77	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	11 ms	13308 KiB

mushrooms

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;

void solve(){

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

    vector<string>grid(r);

    for(ll i = 0; i < r; i++){
        string temp;
        cin >> temp;
        grid[i] = temp;
    }
    //cout << "lol" << endl;


    vector<vector<ll>> dp(r + 1, vector<ll>(c + 1, 0));

    for(ll i = 1; i <= r; i++){
        for(ll j = 1; j <= c; j++){
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1];
            if(grid[i - 1][j - 1] == 'S'){
                dp[i][j]++;
            }
        }
    }

    ll total = 0;
    for(ll i = 0; i < r; i++){
        for(ll j = 0; j < c; j++){
            if(grid[i][j] == 'M'){
                ll temp = 0;
                temp += dp[min(i + d + 1, r)][min(j + d + 1, c)];
                temp -= dp[min(i + d + 1, r)][max(0LL, j - d)];
                temp -= dp[max(0LL, i - d)][min(j + d + 1, c)];
                temp += dp[max(0LL, i - d)][max(0LL, j - d)];
                if(temp >= k){
                    total++;
                }
            }
        }
    }
    cout << total << endl;




}

bool single = true;

int main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if(!single) cin >> t;

    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