Submission #499592

#	Time	Username	Problem	Language	Result	Execution time	Memory
499592		Marceantasy	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	156 ms	18972 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define ar array

const int mxN = 3005, M = 1e9+7; 
int n, m, dp[3][mxN], ans = 0;
string s[mxN];

inline bool c(int x, int y, char c){
    return x>=0&&x<n&&y>=0&&y<m&&s[x][y]==c;
}

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i<n; ++i){
        cin >> s[i];
    }
    for(int i = 0; i<n+m-3; ++i){
        int border = min(m, i+2);
        for(int j = 0; j<border; ++j){
            dp[0][j+1] = max(dp[0][j], max(dp[1][j], dp[2][j]));
            if(c(i-j+1, j-1, 'R') && c(i-j+1, j, 'G') && c(i-j+1, j+1, 'W')){
                dp[1][j+1] = max(dp[0][j], dp[1][j])+1;
            }else{
                dp[1][j+1] = 0;
            }
            if(c(i-j, j, 'R') && c(i-j+1, j, 'G') && c(i-j+2, j, 'W')){
                dp[2][j+1] = max(dp[0][j], dp[2][j])+1;
            }else{
                dp[2][j+1] = 0;
            }
        }
        ans += max(dp[0][border], max(dp[1][border], dp[2][border]));
    }
    cout << ans << "\n";
}

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