Submission #197004

#	Time	Username	Problem	Language	Result	Execution time	Memory
197004		combi1k1	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	326 ms	18172 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 3005;

typedef pair<int,int>   ii;

char a[N][N];
int  f[N][2][2];

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

    int n;  cin >> n;
    int m;  cin >> m;

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

    int ans = 0;

    for(int d = 1 ; d < n + m ; ++d)    {
        int r = 1;
        int c = d;

        if (c > m)  r += (c - m),   c = m;
        if (r > n)  c += (r - n),   r = n;

        int len = min(n - r + 1,c);

        for(int i = 1 ; i <= len ; ++i)
            f[i][0][0] = f[i][0][1] = 0,
            f[i][1][0] = f[i][1][1] = 0;

        for(int i = 1 ; i <= len ; ++i, ++r, --c)   {
            for(int j = 0 ; j < 2 ; ++j)
            for(int k = 0 ; k < 2 ; ++k)
                f[i][k][0] = max(f[i][k][0],f[i - 1][j][k]);

            if (a[r][c] == 'R') {
                if (a[r + 1][c] == 'G' && a[r + 2][c] == 'W')   {
                    f[i][0][1] = max(f[i][0][1],f[i][0][0] + 1);
                    f[i][1][1] = max(f[i][1][1],f[i][1][0] + 1);
                }
                if (a[r][c + 1] == 'G' && a[r][c + 2] == 'W')
                    f[i][0][0] = max(f[i][0][0],f[i - 1][0][0] + 1);
            }
        }
        int cur = 0;

        for(int i = 1 ; i <= len ; ++i)
        for(int j = 0 ; j < 2 ; ++j)
        for(int k = 0 ; k < 2 ; ++k)
            if (cur < f[i][j][k])
                cur = f[i][j][k];

        ans += cur;
    }
    cout << ans << endl;
}

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