Submission #933088

#	Time	Username	Problem	Language	Result	Execution time	Memory
933088		Do_you_copy	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	21 ms	32156 KiB

mushrooms

#include <bits/stdc++.h>
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
int r, c, d, k;
const int maxN = 5e5 + 10;
vector <int> a[maxN];
vector <int> b[maxN];
void update(int i, int j, int x){
    // truong hop nam ngoai mang
    if (i > r || j > c) return;
    // truong hop nam truoc mang
    // can day vi tri cua i j len nho nhat la 1
    // vi du: i j = -1, -3 thi vi tri tuog ung can update la 1 1
    // i j = -3 6 thi vi tri tuong ung can update la 1 6
    i = max(i, 1);
    j = max(j, 1); 
    a[i][j] += x;

}
void Init(){
    // nhap cac du lieu r c d k
    cin >> r >> c >> d >> k;
    // khai bao mang 2 chieu gom r dong c cot
    // do r * c <= 500000 nen chung ta se su dung 500000 mang dong sau do tuy bien voi c sau
    for (int i = 0; i <= r; ++i){
        // Set size 1 dong thanh c + 1 cot (tinh tu 0 den c)
        a[i].resize(c + 1);
        b[i].resize(c + 1);
    }
    for (int i = 1; i <= r; ++i){
        for (int j = 1; j <= c; ++j){
            // nhap du lieu bang
            char tem; cin >> tem;
            if (tem == '.')continue;
            else if (tem == 'M'){
                // danh dau o nay la nam
                b[i][j] = 1;
            }
            else{
                // neu nhu la voi nuoc
                // su dung tinh chat cua mang hieu de tang tat ca cac o xung quanh len 1
                // viet 1 ham de update cho chuan, trong truong hop o update nam ngoai mang minh con xu li cho de
                update(i - d, j - d, 1);
                update(i + d + 1, j - d, -1);
                update(i - d, j + d + 1, -1);
                update(i + d + 1, j + d + 1, 1);
            }
        }
    }
    int ans = 0;
    // cong don lai ca mang
    for (int i = 1; i <= r; ++i){
        for (int j = 1; j <= c; ++j){
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            if (b[i][j] == 1){
                // Neu la nam va duoc tuoi boi nhieu hon k voi
                if (a[i][j] >= k){
                    ++ans;
                }
            }
        }
    }
    cout << ans;

}

signed main(){
    faster;
    Init();

}

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