oj.uz

Submission #1006040

# Submission time Handle Problem Language Result Execution time Memory
1006040 2024-06-23T10:34:45 Z kebine Collecting Mushrooms (NOI18_collectmushrooms) C++17
38 / 100
 39 ms 59076 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
bool ckmin(int& a, int b){return b < a ? a = b, 1 : 0;}
bool ckmax(int& a, int b){return b > a ? a = b, 1 : 0;}
const int N = 2e5 + 5, mod = 1e9 + 7;
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, m, d, s; cin >> n >> m >> d >> s;
    int p[n + 2][m + 2], p2[n + 2][m + 2];
    char g[n + 2][m + 2];
    int l[n + 2][m + 2], r[n + 2][m + 2];
    memset(l, 0, sizeof(l));
    memset(r, 0, sizeof(r));
    memset(p, 0, sizeof(p));
    memset(p2, 0, sizeof(p2));
    vector<pii> lol;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if(g[i][j] == 'S') {
                int i1 = max((int)1, i - d), i2 = min(n, i + d), j1 = max((int)1, j - d), j2 = min(m, j + d);
                l[i1][j1]++, r[i2][j2]++;
                // cout << i1 << " " << i2 << " " << j1 << " " << j2 << endl;
            } else if(g[i][j] == 'M') lol.pb({i, j});
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + l[i][j];
            p2[i][j] = p2[i - 1][j] + p2[i][j - 1] - p2[i - 1][j - 1] + r[i][j];
            // cout << i << " " << j << " " << p[i][j] << " " << p2[i][j] << endl;
        }
    }
    int ans = 0;
    for(auto i : lol) {
        int a = i.fi, b = i.se;
        int tmp = p[a][b] - p2[a - 1][b] - p2[a][b - 1] + p2[a - 1][b - 1];
        if(tmp >= s) ans++;
        // cout << a << " " << b << " " << tmp << endl;
    }
    cout << ans << endl;


}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 23.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 53684 KB Output is correct
2 Correct 38 ms 58056 KB Output is correct
3 Correct 36 ms 59076 KB Output is correct
4 Correct 36 ms 53584 KB Output is correct
5 Correct 39 ms 57400 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 344 KB Output isn't correct
12 Halted 0 ms 0 KB -