Submission #88216

#	Time	Username	Problem	Language	Result	Execution time	Memory
88216		tieunhi	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	527 ms	178344 KiB

dango_maker

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define N 3005

using namespace std;

int n, m, dp[N][3], dd[N][N][3], cur;
char c[N][N];
pii a[N];
int solve()
{
    FOR(i, 0, cur)
        FOR(j, 0, 2) dp[i][j] = 0;
    int ans = 0;
    FOR(i, 1, cur)
    {
        dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
        if (dd[a[i].F][a[i].S][1])
            dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + 1;
        if (dd[a[i].F][a[i].S][2])
            dp[i][2] = max(dp[i-1][0], dp[i-1][2]) + 1;

        ans = max({ans, dp[i][0], dp[i][1], dp[i][2]});
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> m;
    FOR(i, 1, n)
        FOR(j, 1, m) cin >> c[i][j];
    FOR(i, 1, n)
        FOR(j, 1, m)
        {
            if (c[i][j-1] == 'R' && c[i][j] == 'G' && c[i][j+1] == 'W')
                dd[i][j][1] = 1;
            if (c[i-1][j] == 'R' && c[i][j] == 'G' && c[i+1][j] == 'W')
                dd[i][j][2] = 1;
        }
    int res = 0;

    FOR(i, 2, n+m)
    {
        cur = 0;
        FOR(j, 1, n)
            if (i - j > 0 && i - j <= m) a[++cur] = mp(j, i-j);
        res += solve();
    }
    cout <<res;
}

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