제출 #653146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653146		someone	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	274 ms	161204 KiB

dango_maker

#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';
}

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