제출 #653146

#제출 시각아이디문제언어결과실행 시간메모리
653146someoneDango Maker (JOI18_dango_maker)C++14
100 / 100
274 ms161204 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e3 + 42;

char c[N][N];
int n, m, dp[N][N][2];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    n += 3;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            c[i][j] = '#';
    for(int i = 3; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> c[i][j];
    int ans = 0;
    for(int i = 3; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W') {
                dp[i][j][0] = max(dp[i-1][j+1][0], dp[i-1][j+1][1]) + 1;
            }
            if(c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W') {
                dp[i][j][1] = max(dp[i-3][j+3][0], dp[i-1][j+1][1]) + 1;
            }
            
            dp[i][j][1] = max(dp[i][j][1], dp[i-2][j+2][0]);
            dp[i][j][1] = max(dp[i][j][1], dp[i-1][j+1][1]);
            
            dp[i][j][0] = max(dp[i][j][0], dp[i][j][1]);
            dp[i][j][0] = max(dp[i][j][0], dp[i-1][j+1][0]);
        
            if(i == n-1 || j == 0)
                ans += dp[i][j][0];
        }
    }
    
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...