oj.uz

Submission #666743

# Submission time Handle Problem Language Result Execution time Memory
666743 2022-11-29T13:47:46 Z Ai7081 Collecting Mushrooms (NOI18_collectmushrooms) C++17
0 / 100
 15 ms 16048 KB 
#include <bits/stdc++.h>
using namespace std;

int r, c, d, k, out;
string s;
vector<vector<int>> sum;
vector<pair<int, int>> vp;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> r >> c >> d >> k;
    sum.assign(r+5, vector<int>(c+5, 0));// = vector<int>(r+5, vector<int>(c+5));
    for (int i=0; i<r; i++) {
        cin >> s;
        for (int j=0; j<c; j++) {
            if (s[j] == 'S') {
                int x0=max(0, i+1-d), x1=min(r+1, i+1+d+1), y0=max(0, j+1-d), y1=min(c+1, j+1+d+1);
                sum[x0][y0]++;
                sum[x0][y1]--;
                sum[x1][y0]--;
                sum[x1][y1]++;
            }
            else if (s[j] == 'M') vp.push_back({i, j});
        }
    }
    // for (int i=0; i<=r+1; i++) {for (int j=0; j<=c+1; j++) cout << sum[i][j] << ' '; cout << endl;}
    for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) sum[i][j]+=sum[i-1][j]+sum[i][j-1];
    for (auto [x, y] : vp) if (sum[x+1][y+1] >= k) out++;
    // for (int i=1; i<=r; i++) {for (int j=1; j<=c; j++) cout << sum[i][j] << ' '; cout << endl;}
    cout << out;
    return 0;
}

/*
5 5 1 1
....M
.M...
..S..
.S...
...M.

1 8 5 2
SM..MM.S

5 5 2 2
....M
.M...
..S..
.S...
...M.
*/

Subtask #1
0 / 9.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 21.0

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