Submission #509179

#	Time	Username	Problem	Language	Result	Execution time	Memory
509179		cig32	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	727 ms	88416 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

vector<int> active;

int32_t main() {
    int n, m;
    cin >> n >> m;
    char a[n+1][m+1];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }
    int dp[n+1][m+1][2];
    for(int i=0; i<=n; i++) {
        for(int j=0; j<=m; j++) {
            dp[i][j][0] = dp[i][j][1] = 0;
        }
    }
    int ans = 0;
    for(int i=2; i<=n+m; i++) {
        int r, c;
        if(i <= m + 1) r = 1, c = i - 1;
        else c = m, r = i - m;
        int cm = i;
        dp[r][c][0] = (c>1 && c<m && a[r][c-1] == 'R' && a[r][c] == 'G' && a[r][c+1] == 'W');
        dp[r][c][1] = (r>1 && r<n && a[r-1][c] == 'R' && a[r][c] == 'G' && a[r+1][c] == 'W');
        int mx = max(dp[r][c][0], dp[r][c][1]);
        while(r+1 <= n && c-1 >= 1) {
            r++, c--;
            dp[r][c][0] = max(
                dp[r-1][c+1][0] + (c>1 && c<m && a[r][c-1] == 'R' && a[r][c] == 'G' && a[r][c+1] == 'W'),
                dp[r-1][c+1][1]
            );
            dp[r][c][1] = max(
                dp[r-1][c+1][0],
                dp[r-1][c+1][1] + (r>1 && r<n && a[r-1][c] == 'R' && a[r][c] == 'G' && a[r+1][c] == 'W')
            );
            mx = max(mx, dp[r][c][0]);
            mx = max(mx, dp[r][c][1]);
        }
        ans += mx;
    }
    
    cout << ans << "\n";
    
}

Compilation message (stderr)

dango_maker.cpp: In function 'int32_t main()':
dango_maker.cpp:26:13: warning: unused variable 'cm' [-Wunused-variable]
   26 |         int cm = i;
      |             ^~

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