Submission #680137

#	Time	Username	Problem	Language	Result	Execution time	Memory
680137		Duy_e	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	1 ms	340 KiB

dango_maker

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i ++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i --)
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;

ll dp[N][3], n, m, ans;
char a[3005][3005];

bool check(char a, char b, char c) {
    return a == 'R' && b == 'G' && c == 'W';
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        //freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
    
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) cin >> a[i][j];

    rep(s, 2, n + m) {
        
        ll res = 0;
        rep(j, 1, m) dp[j][1] = dp[j][2] = 0;

        rep(j, 1, m) {
            int i = s - j;
            // dp[j][0] = dp[j][1] = dp[j][2] = 0;
            dp[j][1] = dp[j - 1][1];
            dp[j][2] = dp[j - 1][2];
            if (i < 1 || i > n) continue;

            // 0: nothing
            // 1: vertical
            // 2: horizontal
            // if (s == 4) cout << i << ' ' << j << '\n';


            if (i > 2 && check(a[i - 2][j], a[i - 1][j], a[i][j]))
                dp[j][1] = max(dp[j][1], max(dp[j - 1][1], j > 3 ? dp[j - 3][2] : 0) + 1);
            
            if (j > 2 && check(a[i][j - 2], a[i][j - 1], a[i][j]))
                dp[j][2] = max(dp[j][2], max(dp[j - 1][2], j > 3 ? dp[j - 3][1] : 0) + 1);
        
            res = max(res, max(dp[j][1], dp[j][2]));
        }

        // cout << s << ": " << res << '\n';

        ans += res;
    }

    cout << ans << '\n';

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message (stderr)

dango_maker.cpp:66:9: warning: "/*" within comment [-Wcomment]
   66 | /**  /\_/\
      |

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