Submission #1155738

#TimeUsernameProblemLanguageResultExecution timeMemory
1155738dostsDango Maker (JOI18_dango_maker)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e3+1,MOD =  998244353;

void solve() {  
    int n,m;
    cin >> n >> m;
    vector<string> grid(n);
    for (auto& it : grid) cin >> it;
    auto down = [&](int r,int c) {
        if (r+2 >= n || r < 0) return false;
        if (c >= m || c < 0) return false;
        return grid[r][c] == 'R' && grid[r+1][c] == 'G' && grid[r+2][c] == 'W';
    };
    auto right = [&](int r,int c) {
        if (c+2 >= m) return false;
        return grid[r][c] == 'R' && grid[r][c+1] == 'G' && grid[r][c+2] == 'W';
    };

    int ans = 0;
    for (int i=1;i<=n+m-1;i++) {
        int topx = (i <= m) ? (1) : (i-m+1);
        int topy = (i <= m) ? (i) : (m);
        int dp[n+2]{};
        int mx = 0;
        for (int ctr = 1;topx <= n && topy >= 1;topx++,topy--,ctr++) {
            if (right(topx-1,topy-1)) {
                dp[ctr+1] = max(dp[ctr+1],dp[ctr]+1);
            }
            if (down(topx-1,topy-1)) {
                dp[min(n+1,ctr+3)] = max(dp[min(n+1,ctr+3)],dp[ctr]+down(topx-1,topy-1)+down(topx,topy-2)+down(topx+1,topy-3));
            }
        }
        for (int i = 0;i<=n+1;i++) mx = max(mx,dp[i]);
        ans+=mx;
    }
    cout << ans << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...