제출 #369250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369250		Lam_lai_cuoc_doi	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	277 ms	18304 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 3e3 + 5;
const ll Inf = 1e17;
int n, m;
string s[N];
int dp[N][2];

void Read()
{
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i];
        s[i] = " " + s[i];
    }
}

inline void Max(int &x, int y)
{
    if (x < y)
        x = y;
}

void Solve()
{
    int ans(0);
    for (int t = 4; t <= m + n; ++t)
    {
        for (int i = 1; i <= n; ++i)
            dp[i][0] = dp[i][1] = 0;
        for (int i = t <= m ? 1 : t - m; i < t && i <= n; ++i)
        {
            if (i > 2 && s[t - i][i - 2] == 'R' && s[t - i][i - 1] == 'G' && s[t - i][i] == 'W')
                ++dp[i][0];
            if (t - i > 2 && s[t - i - 2][i] == 'R' && s[t - i - 1][i] == 'G' && s[t - i][i] == 'W')
                ++dp[i][1];
            Max(dp[i + 1][0], dp[i][0]);
            Max(dp[i + 1][1], dp[i][0]);
            Max(dp[i + 3][0], dp[i][1]);
            Max(dp[i + 1][1], dp[i][1]);
        }
        ans += max(dp[min(t - 1, n)][0], dp[min(t - 1, n)][1]);
    }
    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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