oj.uz

Submission #1060430

# Submission time Handle Problem Language Result Execution time Memory
1060430 2024-08-15T14:16:25 Z Kazoo Collecting Mushrooms (NOI18_collectmushrooms) C++14
38 / 100
 19 ms 34532 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxR = 5e5+5;
int r, c, d, k;
string garden[maxR];



int main(){
    // bool watered[maxR][maxR];
    // memset(watered, false, sizeof(watered));

    cin >> r >> c >> d >> k;
    for(int i = 0; i<r; i++){
        cin >> garden[i];
    }
    vector<vector<bool>> watered;
    vector<vector<int>> kena;
    for(int i = 0; i<r; i++){
        vector<int> ps;
        vector<bool> ps1;
        for(int j = 0; j<c; j++){
            ps.push_back(0);
            ps1.push_back(false);
        }
        kena.push_back(ps);
        watered.push_back(ps1);
    }

    for(int i = 0; i<r; i++){
        for(int j = 0; j<c; j++){
            if(garden[i][j]=='S')
            {
                // atas kiri [i-d][j-d]
                // bawah kanan [i+d][j+d]
                // atas kanan [i-d][j+d]
                // bawah kiri [i+d][j-d]

                int atas = max(i-d, 0);
                int kiri = max(j-d, 0);
                kena[atas][kiri]++;
                int kanan = -1, bawah = -1;
                if(i+d+1<=r-1) bawah = i+d+1;
                if(j+d+1<=c-1) kanan = j+d+1;

                if(kanan!=-1) kena[atas][kanan]--;
                if(bawah!=-1) kena[bawah][kiri]--;
                if(kanan!=-1 && bawah!=-1) kena[kanan][bawah]++;
                
            }
        }
    }   

    ll ans = 0;
    for(int i = 0; i<r; i++){
        for(int j = 0; j<c; j++){
            if(i!=0) kena[i][j] += kena[i-1][j];
            if(j!=0) kena[i][j] += kena[i][j-1];
            if(i!=0 && j!=0) kena[i][j] -= kena[i-1][j-1];

            if(garden[i][j]=='M' && kena[i][j] >= k) ans++;
        }
        // cout << endl;
    } 

    cout << ans << endl;

}

Subtask #1
9.0 / 9.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 16164 KB Output is correct
3 Correct 6 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 15960 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 32348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17240 KB Output is correct
2 Runtime error 19 ms 34532 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 21516 KB Output is correct
2 Correct 15 ms 21516 KB Output is correct
3 Correct 19 ms 21328 KB Output is correct
4 Correct 17 ms 21512 KB Output is correct
5 Correct 17 ms 21516 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 16164 KB Output is correct
3 Correct 6 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 15960 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 4 ms 16220 KB Output is correct
11 Runtime error 18 ms 32348 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -