제출 #1351170

#제출 시각아이디문제언어결과실행 시간메모리
1351170guardianecDango Maker (JOI18_dango_maker)C++20
100 / 100
146 ms9444 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[3007][3];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n,m;
    cin >> n >> m;
    vector<vector<char>> a(n+1, vector<char>(m+1));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }

    ll res = 0;
    for (int d=2; d<=n+m; d++) {
        ll is = max(d-m, 1LL);
        ll ie = min(n, d-1LL);
        vector<ll> v;
        for (int i=is; i<=ie; i++) {
            ll j = d-i;
            if (a[i][j]=='G') v.push_back(i);
        }

        if (v.empty()) continue;
        ll k = v.size();

        for (int i=0; i<=k; i++) dp[i][0] = dp[i][1] = dp[i][2] = -1e18;

        dp[0][0] = 0;
        for (int k1=1; k1<=k; k1++) {
            ll i = v[k1-1];
            ll j = d-i;
            dp[k1][0] = max({dp[k1-1][0], dp[k1-1][1], dp[k1-1][2]});

            bool c1 = (i>1 && i<n && a[i-1][j]=='R' && a[i+1][j]=='W');
            bool c2 = (j>1 && j<m && a[i][j-1]=='R' && a[i][j+1]=='W');

            bool c3 = (k1>1 && v[k1-2]==i-1);

            if (c1) {
                if (c3) dp[k1][1] = max(dp[k1-1][0], dp[k1-1][1])+1;
                else dp[k1][1] = max({dp[k1-1][0], dp[k1-1][1], dp[k1-1][2]})+1;
            } 

            if (c2) {
                if (c3) dp[k1][2] = max(dp[k1-1][0], dp[k1-1][2])+1;
                else dp[k1][2] = max({dp[k1-1][0], dp[k1-1][1], dp[k1-1][2]})+1;
            }
        }

        res+=max({dp[k][0], dp[k][1], dp[k][2]});
    }

    cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...