Submission #915663

#	Time	Username	Problem	Language	Result	Execution time	Memory
915663		efedmrlr	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	249 ms	27236 KiB

dango_maker

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e3+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;
vector<string> a(N, string(N, '0'));
array<array<int,2>, 2> dp, dpn;
int ans = 0;

inline void solve() {
    cin>>n>>m;
    for(int i = 1; i<=n; i++) {
        cin>>a[i];
        a[i] = '0' + a[i] + "000";
    }   
    for(int t = 2; t<=n + m; t++) {
        dp = {0,0,0,0};
        for(int i = max(1, t - m); i <= n; i++) {
            int j = t - i;
            if(j < 1) break;

            if(a[i][j] != 'R') {
                dp[0][0] = max(dp[0][0], dp[0][1]);
                dp[0][1] = max(dp[1][0], dp[1][1]);
                dp[1][0] = dp[1][1] = 0;
                continue;
            }

            for(int f1 = 0; f1<2; f1++) {
                for(int f2 = 0; f2<2; f2++) {
                    
                    dpn[f1][f2] = 0;
                    if(f1) {
                        if(a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
                            dpn[f1][f2] = max(dp[f2][0], dp[f2][1]) + 1;
                        }
    
                    }
                    else {
                        if(!f2 && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') {
                            dpn[f1][f2] = dp[0][0] + 1;
                        } 
                        dpn[f1][f2] = max(dpn[f1][f2], max(dp[f2][0], dp[f2][1])); 
                    }
                }
            }
            swap(dpn, dp);
        }
        ans += max(max(dp[0][0], dp[0][1]) , max(dp[1][0], dp[1][1]) );
    }
    cout << ans << "\n";
   

}
 
signed main() {

    //fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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