Submission #644014

#	Time	Username	Problem	Language	Result	Execution time	Memory
644014		tokyo682	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	316 ms	123948 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;
 
int dp[3002][3002][3];
string table[3001];

int main(){
    
    int m , n ; cin >> m >> n ;

    for(int i = 1 ; i <= m ; i ++ ){
        cin >> table[i] ;
        table[i] = ' ' + table[i] ;
    }

    for(int i = 1 ; i <= m ; i ++ ){
        for(int j = 1 ; j <= n ; j ++ ){
            if(table[i][j] == 'G'){
                if(j > 1 && j < n){
                    if(table[i][j - 1] == 'R' && table[i][j + 1] == 'W'){
                        dp[i][j][1] = max(dp[i - 1][j + 1][1] , dp[i - 1][j + 1][0]) + 1 ;
                    }
                }
                if(i > 1 && i < m){
                    if(table[i - 1][j] == 'R' && table[i + 1][j] == 'W'){
                        dp[i][j][2] = max(dp[i - 1][j + 1][2] , dp[i - 1][j + 1][0]) + 1 ;
                    }
                }
            }
            dp[i][j][0] = max({dp[i - 1][j + 1][0] , dp[i - 1][j + 1][1] , dp[i - 1][j + 1][2]}) ;
        }
    }
    
    int res = 0 ;
    for(int i = 1 ; i <= m ; i ++ ){
        res += max({dp[i][1][0] , dp[i][1][1] , dp[i][1][2]});
    }
    for(int j = 1 ; j <= n ; j ++ ){
        res += max({dp[m][j][0] , dp[m][j][1] , dp[m][j][2]}) ;
    }
    res -= max({dp[m][1][0] , dp[m][1][1] , dp[m][1][2]});

    cout << res ;
    
    // for(int i = 1 ; i <= m ; i ++ ){
    //     for(int j = 1 ; j <= n ; j ++){
    //         cout << max({dp[i][j][0] , dp[i][j][1] , dp[i][j][2]});
    //     }
    //     cout << '\n';
    // }
    return 0;
}

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