Submission #1155740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155740		dosts	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	130 ms	10388 KiB

dango_maker

#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][3]{};
        int mx = 0;
        for (int ctr = 1;topx <= n && topy >= 1;topx++,topy--,ctr++) {
            for (int j = 0;j<3;j++) {
            dp[ctr+1][max(0ll,j-1)] = max(dp[ctr+1][max(0ll,j-1)],
                                          dp[ctr][j]+(j==0 && right(topx-1,topy-1)));
            dp[ctr+1][2] = max(dp[ctr+1][2],dp[ctr][j]+down(topx-1,topy-1));
            }
        }
        for (int i = 0;i<=n+1;i++) for (int j = 0;j<3;j++) mx = max(mx,dp[i][j]);
        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();
}

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