Submission #933087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
933087	2024-02-25T01:55:04 Z	vjudge1	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	18 / 100	18 ms	32008 KB

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 - k, j - k, 1);
                update(i + k + 1, j - k, -1);
                update(i - k, j + k + 1, -1);
                update(i + k + 1, j + k + 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
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	23896 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	23896 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	23896 KB	Output is correct
2	Correct	6 ms	23896 KB	Output is correct
3	Correct	6 ms	23900 KB	Output is correct
4	Correct	6 ms	23900 KB	Output is correct
5	Correct	5 ms	23900 KB	Output is correct