제출 #1050624

#제출 시각아이디문제언어결과실행 시간메모리
1050624vjudge1Dango Maker (JOI18_dango_maker)C++17
100 / 100
180 ms115904 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<long long,long long> pl;

#define all(s) s.begin(),s.end()
#define F first
#define S second
#define sz(a) a.size()

const ll mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9+200;
const int maxn=3020;

int n,m;
ll ans=0;
char a[maxn][maxn];
int dp[3][maxn][maxn]; 


int H(int i,int j) {
    return (a[i][j-1]=='R'&&a[i][j]=='G'&&a[i][j+1]=='W');
}

int V(int i,int j) {
    return (a[i-1][j]=='R'&&a[i][j]=='G'&&a[i+1][j]=='W');
}

void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=m;++j) {
            dp[0][i][j]=max(dp[0][i-1][j+1],max(dp[1][i-1][j+1],dp[2][i-1][j+1]));
            dp[1][i][j]=max(dp[0][i-1][j+1],dp[1][i-1][j+1]) + H(i,j);
            dp[2][i][j]=max(dp[0][i-1][j+1],dp[2][i-1][j+1]) + V(i,j);
        }
    }
    for(int i=1;i<=n;++i) {
        ans+=(max(dp[0][i][1],max(dp[1][i][1],dp[2][i][1])));
    }
    for(int j=2;j<=m;++j) {
        ans+=(max(dp[0][n][j],max(dp[1][n][j],dp[2][n][j])));
    }
    cout<<ans;
}  

int main() {
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) {
        solve();
    }
    return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...