제출 #1304892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304892		polishprogrammer	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	360 ms	151464 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n + 2, vector<char>(m + 2));
    vector<vector<pair<int, int>>> dasie(n + 2, vector<pair<int, int>>(m + 2, {0, 0})), dp(n + 2, vector<pair<int, int>>(m + 2, {0, 0}));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i > 1 and i < n and grid[i - 1][j] == 'R' and grid[i][j] == 'G' and grid[i + 1][j] == 'W') dasie[i][j].fi = 1;
            if (j > 1 and j < m and grid[i][j - 1] == 'R' and grid[i][j] == 'G' and grid[i][j + 1] == 'W') dasie[i][j].se = 1;
        }
    }
    int wyn = 0;
    for (int i = 1; i < n + m - 1; i++) {
        int kon = 0;
        for (int j = i; j > 0; j--) {
            if (i - j + 1 > n or j > m) continue;
            // aktualny punkt na gridzie to (i - j + 1, j)
            int best = max(dp[i - j][j + 1].fi, dp[i - j][j + 1].se);
            dp[i - j + 1][j].fi = max(best, dp[i - j][j + 1].fi + dasie[i - j + 1][j].fi);
            dp[i - j + 1][j].se = max(best, dp[i - j][j + 1].se + dasie[i - j + 1][j].se);
            kon = max(kon, max(dp[i - j + 1][j].fi, dp[i - j + 1][j].se));
        }
        wyn += kon;
    }
    cout << wyn << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67