Submission #1325775

#TimeUsernameProblemLanguageResultExecution timeMemory
1325775sh_qaxxorov_571Dango Maker (JOI18_dango_maker)C++20
0 / 100
0 ms332 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int N, M;
vector<string> grid;

// Gorizontal tayoqcha bormi? (R-G-W)
bool is_h(int r, int c) {
    if (c + 2 >= M) return false;
    return grid[r][c] == 'R' && grid[r][c+1] == 'G' && grid[r][c+2] == 'W';
}

// Vertikal tayoqcha bormi? (R-G-W)
bool is_v(int r, int c) {
    if (r + 2 >= N) return false;
    return grid[r][c] == 'R' && grid[r+1][c] == 'G' && grid[r+2][c] == 'W';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    grid.resize(N);
    for (int i = 0; i < N; i++) cin >> grid[i];

    int total_sticks = 0;

    // Har bir diagonalni alohida ko'rib chiqamiz
    // i + j = sum (0 dan N + M - 2 gacha)
    for (int sum = 0; sum <= N + M - 2; sum++) {
        vector<int> states; // 1: Gorizontal, 2: Vertikal, 0: Yo'q
        
        for (int r = max(0, sum - (M - 1)), c = sum - r; r < N && c >= 0; r++, c--) {
            int state = 0;
            if (is_h(r, c)) state |= 1;
            if (is_v(r, c)) state |= 2;
            states.push_back(state);
        }

        if (states.empty()) continue;

        int len = states.size();
        // dp[i][mask] - joriy katakda qaysi turdagi tayoqcha borligi
        // mask: 0 (hech narsa), 1 (gorizontal), 2 (vertikal)
        vector<vector<int>> dp(len + 1, vector<int>(3, 0));

        for (int i = 0; i < len; i++) {
            // Holat 0: Hech narsa tanlamaslik
            dp[i+1][0] = max({dp[i][0], dp[i][1], dp[i][2]});

            // Holat 1: Gorizontal (faqat agar grid[r][c...c+2] R-G-W bo'lsa)
            if (states[i] & 1) {
                // Gorizontal tayoqcha keyingi 2 ta diagonal kataklari bilan to'qnashmaydi
                dp[i+1][1] = max(dp[i][0], dp[i][1]) + 1;
            }

            // Holat 2: Vertikal (faqat agar grid[r...r+2][c] R-G-W bo'lsa)
            if (states[i] & 2) {
                // Vertikal tayoqcha ham oldingi holatlarga bog'liq
                dp[i+1][2] = max(dp[i][0], dp[i][2]) + 1;
            }
        }
        total_sticks += max({dp[len][0], dp[len][1], dp[len][2]});
    }

    cout << total_sticks << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...