Submission #477544

#	Time	Username	Problem	Language	Result	Execution time	Memory
477544		FireGhost1301	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	207 ms	123724 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;

const int N = 3e3 + 3;
int n, m, dp[N][N][3];
char c[N][N];

inline bool check(char x, char y, char z) {
    return (x == 'R' && y == 'G' && z == 'W');
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            cin >> c[i][j];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j][0] = max({dp[i - 1][j + 1][0], dp[i - 1][j + 1][1], dp[i - 1][j + 1][2]});
            if (check(c[i - 1][j], c[i][j], c[i + 1][j]))
                dp[i][j][1] = 1 + max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]);
            if (check(c[i][j - 1], c[i][j], c[i][j + 1]))
                dp[i][j][2] = 1 + max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][2]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += max({dp[i][1][0], dp[i][1][1], dp[i][1][2]});
    for (int i = 2; i <= m; ++i) ans += max({dp[n][i][0], dp[n][i][1], dp[n][i][2]});
    cout << ans;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

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