제출 #1102109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1102109		_8_8_	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	280 ms	181868 KiB

dango_maker

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
    
const int  N = 3e3 + 12, MOD = 998244353, M = 3e6 + 12;
    
char a[N][N];
int n, m, ok[N][N][2], dp[N * 2][3];
vector<array<int, 2>> e[N * 2];
void test() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(a[i][j] == 'G' && a[i][j - 1] == 'R' && a[i][j + 1] == 'W') {
                ok[i][j][0] = 1;
            }
            if(a[i][j] == 'G' && a[i - 1][j] == 'R' && a[i + 1][j] == 'W') {
                ok[i][j][1] = 1;
            }
            e[i + j].push_back({i, j});
        }
    }
    int res = 0;
    for(int i = 1; i <= n + m; i++) {
        int f = (int)e[i].size() - 1;
        if(e[i].empty()) continue;
        dp[0][0] = ok[e[i][0][0]][e[i][0][1]][0];
        dp[0][1] = ok[e[i][0][0]][e[i][0][1]][1];
        dp[0][2] = 0;
        for(int j = 1; j < (int)e[i].size(); j++)  {
            int x = e[i][j][0], y = e[i][j][1];
            dp[j][2] = max({dp[j - 1][0], dp[j - 1][1], dp[j - 1][2]});
            dp[j][0] = max(dp[j - 1][0], dp[j - 1][2]) + ok[x][y][0];
            dp[j][1] = max(dp[j - 1][1], dp[j - 1][2]) + ok[x][y][1];
        }   

        // cout << dp[f][1] << '\n';
        res += max({dp[f][0], dp[f][1], dp[f][2]});
    }
    cout << res;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

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