Submission #464200

#	Time	Username	Problem	Language	Result	Execution time	Memory
464200		TeaTime	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	366 ms	71112 KiB

dango_maker

//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 3010, INF = 1e9, LG = 20;
char grid[SZ][SZ];
short dp[SZ][SZ][3];
ll n, m;

bool good(int x, int y, int dir) {
    if (dir == 0) {
        if (grid[x][y] == 'G' && (x - 1 >= 0 && grid[x - 1][y] == 'R') && (x + 1 < n && grid[x + 1][y] == 'W')) return 1;
        return 0;
    }
    if (dir == 1) {
        if (grid[x][y] == 'G' && (y - 1 >= 0 && grid[x][y - 1] == 'R') && (y + 1 < m && grid[x][y + 1] == 'W')) return 1;
        return 0;
    }
}
signed main() {
    fastInp;

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) grid[i][j] = s[j];
    }

    ll ans = 0;
    for (int j = 0; j < m; j++) {
        for (int i = n - 1; i >= 0; i--) {
            ll svd1 = 0, svd2 = 0, svd0 = 0;
            if (i < n - 1 && j > 0) {
                dp[i][j][0] = svd0 = dp[i + 1][j - 1][0];
                dp[i][j][1] = svd1 = dp[i + 1][j - 1][1];
                dp[i][j][2] = svd2 = dp[i + 1][j - 1][2];
            }
            if (good(i, j, 0)) {
                dp[i][j][1] = max(svd0 + 1, svd1 + 1);
            }
            if (good(i, j, 1)) {
                dp[i][j][2] = max(svd0 + 1, svd2 + 1);
            }
            dp[i][j][0] = max(max(svd0, svd1), svd2);

            if (!(i - 1 >= 0 && j + 1 < m)) {
                ans += max(dp[i][j][2], max(dp[i][j][0], dp[i][j][1]));
            }
        }
    }

    cout << ans;

    return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

Compilation message (stderr)

dango_maker.cpp: In function 'bool good(int, int, int)':
dango_maker.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
   33 | }
      | ^

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