Submission #1004920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004920		_callmelucian	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	170 ms	18036 KiB

dango_maker

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

/*
    - dumplings order: R-G-B
    if   G on the i-th diagonal contributes to a stick
    then R is on the (i-1)-th diagonal
         W is on the (i+1)-th diagonal

    - G's on different diagonals are dependent

    - a horizontal and vertical stick on the same
    diagonal can't be placed consecutive.
*/

int dpNot[3003], dpHor[3003], dpVer[3003], n, m;
char a[3003][3003];

bool okHor (int row, int col) {
    if (row - 1 < 1 || row + 1 > n) return 0;
    return a[row - 1][col] == 'R'
        && a[row][col] == 'G'
        && a[row + 1][col] == 'W';
}

bool okVer (int row, int col) {
    if (col - 1 < 1 || col + 1 > m) return 0;
    return a[row][col - 1] == 'R'
        && a[row][col] == 'G'
        && a[row][col + 1] == 'W';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    int ans = 0;
    for (int diag = 2; diag <= n + m; diag++) {
        int mn = max(1, diag - m), mx = min(n, diag - 1);
        for (int row = mn - 1; row <= mx; row++)
            dpNot[row] = dpHor[row] = dpVer[row] = 0;

        for (int row = mn; row <= mx; row++) {
            int col = diag - row;
            dpNot[row] = max(dpNot[row - 1], max(dpHor[row - 1], dpVer[row - 1]));
            if (okHor(row, col)) dpHor[row] = max(dpHor[row - 1], dpNot[row - 1]) + 1;
            if (okVer(row, col)) dpVer[row] = max(dpVer[row - 1], dpNot[row - 1]) + 1;
        }

        ans += max(dpNot[mx], max(dpHor[mx], dpVer[mx]));
    }

    cout << ans;

    return 0;
}

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