oj.uz

Submission #933088

# Submission time Handle Problem Language Result Execution time Memory
933088 2024-02-25T02:02:43 Z Do_you_copy Collecting Mushrooms (NOI18_collectmushrooms) C++17
100 / 100
 21 ms 32156 KB 
#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.0 / 9.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23896 KB Output is correct
2 Correct 6 ms 24052 KB Output is correct
3 Correct 6 ms 24000 KB Output is correct
4 Correct 6 ms 23944 KB Output is correct
5 Correct 6 ms 23896 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Correct 6 ms 23900 KB Output is correct
8 Correct 6 ms 23900 KB Output is correct
9 Correct 6 ms 23900 KB Output is correct
10 Correct 6 ms 23900 KB Output is correct

Subtask #3
18.0 / 18.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25436 KB Output is correct
2 Correct 12 ms 25756 KB Output is correct
3 Correct 11 ms 25948 KB Output is correct
4 Correct 10 ms 25544 KB Output is correct
5 Correct 10 ms 25692 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31716 KB Output is correct
2 Correct 16 ms 32092 KB Output is correct
3 Correct 17 ms 32060 KB Output is correct
4 Correct 21 ms 32156 KB Output is correct
5 Correct 18 ms 32092 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23896 KB Output is correct
2 Correct 6 ms 24052 KB Output is correct
3 Correct 6 ms 24000 KB Output is correct
4 Correct 6 ms 23944 KB Output is correct
5 Correct 6 ms 23896 KB Output is correct
6 Correct 7 ms 23900 KB Output is correct
7 Correct 6 ms 23900 KB Output is correct
8 Correct 6 ms 23900 KB Output is correct
9 Correct 6 ms 23900 KB Output is correct
10 Correct 6 ms 23900 KB Output is correct
11 Correct 6 ms 23900 KB Output is correct
12 Correct 6 ms 23900 KB Output is correct
13 Correct 6 ms 23896 KB Output is correct
14 Correct 6 ms 23896 KB Output is correct
15 Correct 6 ms 23900 KB Output is correct
16 Correct 9 ms 25436 KB Output is correct
17 Correct 12 ms 25756 KB Output is correct
18 Correct 11 ms 25948 KB Output is correct
19 Correct 10 ms 25544 KB Output is correct
20 Correct 10 ms 25692 KB Output is correct
21 Correct 19 ms 31716 KB Output is correct
22 Correct 16 ms 32092 KB Output is correct
23 Correct 17 ms 32060 KB Output is correct
24 Correct 21 ms 32156 KB Output is correct
25 Correct 18 ms 32092 KB Output is correct
26 Correct 18 ms 28880 KB Output is correct
27 Correct 17 ms 28252 KB Output is correct
28 Correct 17 ms 28248 KB Output is correct
29 Correct 16 ms 28252 KB Output is correct
30 Correct 17 ms 28760 KB Output is correct