제출 #1015874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015874		snpmrnhlol	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	505 ms	88404 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3;
char v[N][N];
int n,m;
int ans = 0;
bool ok(int x,int y,int id){
    if(id == 0){
        return 0 <= x && x <= n - 1 && 0 <= y && y <= m - 3 && v[x][y] == 'R' && v[x][y + 1] == 'G' && v[x][y + 2] == 'W';
    }else{
        return 0 <= x && x <= n - 3 && 0 <= y && y <= m - 1 && v[x][y] == 'R' && v[x + 1][y] == 'G' && v[x + 2][y] == 'W';
    }
}
int dp[N][N][2];
int main(){
    cin>>n>>m;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin>>v[i][j];
        }
    }
    for(int i = n - 1;i >= 0;i--){
        for(int j = 0;j < m;j++){
            dp[i][j][0] = max(ok(i,j - 1,0) + (i + 1 < n && j - 1 >= 0?dp[i + 1][j - 1][0]:0),dp[i][j][0]);
            dp[i][j][0] = max(ok(i,j - 1,0) + (i + 2 < n && j - 2 >= 0?dp[i + 2][j - 2][1]:0),dp[i][j][0]);
            dp[i][j][1] = max(ok(i - 1,j,1) + (i + 1 < n && j - 1 >= 0?dp[i + 1][j - 1][1]:0),dp[i][j][1]);
            dp[i][j][1] = max(ok(i - 1,j,1) + (i + 2 < n && j - 2 >= 0?dp[i + 2][j - 2][0]:0),dp[i][j][1]);
            if(i == 0 || j == m - 1){
                ans+=max(dp[i][j][0],dp[i][j][1]);
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}

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