제출 #1195064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195064		nekolie	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	135 ms	80764 KiB

dango_maker

// Papryko, daj lepsze zadanka
#include <bits/stdc++.h>
using namespace std;

int n, m, dp[6000], czy[3000][3000][2];
string dango[3000];
void triv() {
    int odp = 0;
    if (n < 3) {
        for (int i = 0; i < n; i++)
            for (int j = 2; j < m; j++)
                if (dango[i][j-2] == 'R' && dango[i][j-1] == 'G' && dango[i][j] == 'W')
                    odp++;
    }
    else {
        for (int j = 0; j < m; j++)
            for (int i = 2; i < n; i++)
                if (dango[i-2][j] == 'R' && dango[i-1][j] == 'G' && dango[i][j] == 'W')
                    odp++;
    }
    cout << odp << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> dango[i];
    if (min(n,m) < 3)
        triv();
    else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dango[i][j] == 'W') {
                    czy[i][j][0] = ((j > 1 && dango[i][j-2] == 'R' && dango[i][j-1] == 'G' && dango[i][j] == 'W') ? 1 : 0);
                    czy[i][j][1] = ((i > 1 && dango[i-2][j] == 'R' && dango[i-1][j] == 'G' && dango[i][j] == 'W') ? 1 : 0);
                }
                else
                    czy[i][j][0] = czy[i][j][1] = 0;
            }
        }
        for (int i = 2; i < n+m; i++) {
            int x = min(i,n-1), y = i-x, pom[n+m][2], k = 0;
            pom[k][0] = czy[x][y][0], pom[k][1] = czy[x][y][1], k++;
            while (x > 0 && y < m-1) {
                x--, y++,
                pom[k][0] = czy[x][y][0] + max(pom[k-1][0],((k > 2) ? pom[k-3][1] : 0));
                pom[k][1] = czy[x][y][1] + max(pom[k-1][0],pom[k-1][1]), k++;
            }
            dp[i] = dp[i-1] + max(pom[k-1][0],pom[k-1][1]);
        }
        cout << dp[n+m-1] << endl;
    }
    return 0;
}

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