Submission #348578

#	Time	Username	Problem	Language	Result	Execution time	Memory
348578		Nima_Naderi	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	274 ms	36076 KiB

dango_maker

///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e3 + 10;
ll n, m, ans;
ll dp[3][MXN];
string S[MXN];
bool mark[2][MXN][MXN];
ll Calc(ll sum){
    memset(dp, 0, sizeof dp);
    ll now = 0;
    for(int i = 1, j = sum - 1; i <= n; i ++, j --){
        if(i < 1 || i > n) continue;
        if(j < 1 || j > m) continue;
        dp[0][i] = max({dp[0][i - 1], dp[1][i - 1], dp[2][i - 1]});
        if(mark[0][i][j]){
            dp[1][i] = max(dp[0][i - 1], dp[1][i - 1]) + 1;
        }
        if(mark[1][i][j]){
            dp[2][i] = max(dp[0][i - 1], dp[2][i - 1]) + 1;
        }
        now = max({now, dp[0][i], dp[1][i], dp[2][i]});
    }
    return now;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> S[i];
        S[i] = "$" + S[i];
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(S[i][j] != 'G') continue;
            if(j - 1 >= 1 && j + 1 <= m){
                mark[0][i][j] = (S[i][j - 1] == 'R' && S[i][j + 1] == 'W');
            }
            if(i - 1 >= 1 && i + 1 <= n){
                mark[1][i][j] = (S[i - 1][j] == 'R' && S[i + 1][j] == 'W');
            }
        }
    }
    for(int sum = 2; sum <= n + m; sum ++){
        ans += Calc(sum);
    }
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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