Submission #1187825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187825		jerzyk	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	143 ms	80040 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1'000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1'000'000'007LL;
const int N = 3007;
string s[N];
int dp[N][N][2];

void Solve()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        s[i] = '!' + s[i];
    }
    for(int i = 1; i <= n; ++i)
        for(int j = m; j >= 1; --j)
        {
            for(int r = 0; r < 2; ++r)
                dp[i][j][r] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]);
            if(j > 1 && j + 1 <= m && s[i][j - 1] == 'R' && s[i][j] == 'G' && s[i][j + 1] == 'W')
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j + 1][0] + 1);
            if(i > 1 && i + 1 <= n && s[i - 1][j] == 'R' && s[i][j] == 'G' && s[i + 1][j] == 'W')
                dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j + 1][1] + 1);
        }
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        ans += max(dp[i][1][0], dp[i][1][1]);
    for(int j = 2; j <= m; ++j)
        ans += max(dp[n][j][0], dp[n][j][1]);
    cout << ans << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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