Submission #1340452

#TimeUsernameProblemLanguageResultExecution timeMemory
1340452iamhereforfunDango Maker (JOI18_dango_maker)C++20
100 / 100
154 ms9292 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 3e3 + 5;
const int M = 2e5 + 5;
const int LG = 20;
const int INF = 1e9 + 5;
const int K = 2;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;

int n, m, dp[N][2], ans;
char mp[N][N];

inline void solve()
{
    cin >> n >> m;
    memset(mp, 'a', sizeof(mp));
    ans = 0;
    for (int x = 1; x <= n; x++)
    {
        for (int y = 1; y <= m; y++)
        {
            cin >> mp[x][y];
        }
    }
    for (int s = 2; s <= n + m - 2; s++)
    {
        for (int x = 1; x <= n; x++)
        {
            dp[x][0] = dp[x][1] = 0;
        }
        for (int x = max(1, s - m); x <= n; x++)
        {
            dp[x][0] = max(dp[x - 1][0], dp[x - 1][1]);
            dp[x][1] = dp[x - 1][1];
            if (x > 3)
                dp[x][1] = max(dp[x - 3][0], dp[x][1]);
            int y = s - x;
            if (y < 1 || y > m)
                continue;
            if (mp[x][y] == 'R' && mp[x + 1][y] == 'G' && mp[x + 2][y] == 'W') // 0
            {
                dp[x][0]++;
            }
            if (mp[x][y] == 'R' && mp[x][y + 1] == 'G' && mp[x][y + 2] == 'W') // 1
            {
                dp[x][1]++;
            }
        }
        ans += max(dp[n][0], dp[n][1]);
        // cout << ans << " " << s << "\n";
    }
    cout << ans << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...