oj.uz

Submission #521954

# Submission time Handle Problem Language Result Execution time Memory
521954 2022-02-03T13:52:05 Z fallingstar Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 312 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

using namespace std;

int solve(const vector<int>& a)
{
    int n = a.size();
    vector<array<int, 2>> f(n, {-1, -1});
    if (a[0] & 1) f[0][0] = 1;
    if (a[0] & 2) f[0][1] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 2; ++j)
            if (a[i + 1] & (j + 1))
                f[i + 1][j] = max({f[i + 1][j], f[i][1 - j], f[i][j] + 1});
    return max(f.back()[0], f.back()[1]);
}

int main()
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<string> tab(n);
    for (int i = 0; i < n; ++i) cin >> tab[i];

    int res = 0;
    vector<vector<bool>> vst(n, vector<bool>(m));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (tab[i][j] == 'G' && !vst[i][j]) {
                vector<int> seq;
                int u = i, v = j;
                while (true) {
                    int x = 0;
                    x |= (u > 0 && u + 1 < n && tab[u - 1][v] == 'R' && tab[u + 1][v] == 'W');
                    x |= (v > 0 && v + 1 < m && tab[u][v - 1] == 'R' && tab[u][v + 1] == 'W') * 2;
                    if (!x) break;
                    vst[u][v] = true;
                    seq.push_back(x);
                    ++u, --v;
                    if (u >= n || v < 0 || tab[u][v] != 'G') break;
                }
                if (!seq.empty()) res += solve(seq);
            }
    cout << res;
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 268 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 268 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 268 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB Output isn't correct
20 Halted 0 ms 0 KB -