Submission #1164601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164601		tvgk	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	176 ms	9560 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e3 + 7;

int nRow, nCol, dp[mxN][4];
string s[mxN];
int d1[2] = {1, 0};
int d2[2] = {0, 1};
char chr[4] = {'R', 'G', 'W'};

bool Check(int u, int v, bool tt)
{
    if (u < 0 || v < 0)
        return 0;

    for (int i = 0; i < 3; i++)
    {
        if (u > nRow || v > nCol)
            return 0;

        if (s[u][v] != chr[i])
            return 0;

        u += d1[tt];
        v += d2[tt];
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> nRow >> nCol;
    for (int i = 1; i <= nRow; i++)
    {
        cin >> s[i];
        s[i] = ' ' + s[i];
    }

    int ans = 0;
    for (int i = 2; i <= nCol + nRow; i++)
    {
        for (int j = min(nCol, i - 1); j > 0; j--)
        {
            for (int u = 3; u >= 0; u--)
                dp[j][u] = 0;

            for (int u = 3; u >= 0; u--)
                dp[j][max(0, u - 1)] = max(dp[j][max(0, u - 1)], dp[j + 1][u]);

            if (Check(i - j, j, 0))
                dp[j][3] = max({dp[j][0], dp[j][1], dp[j][2]}) + 1;
            if (Check(i - j, j, 1))
                dp[j][0]++;
        }
        ans += max({dp[1][0], dp[1][1], dp[1][2], dp[1][3]});
    }
    cout << ans;
}

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