Submission #204078

#	Time	Username	Problem	Language	Result	Execution time	Memory
204078		Kastanda	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	256 ms	18240 KiB

dango_maker

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 3003;
int n, m, cnt, dp[N][2];
bool M[N][N];
char S[N][N];
inline bool Horz(int i, int j)
{
    if (M[i][j] || M[i][j + 1] || M[i][j + 2])
        return 0;
    return (S[i][j] == 'R' && S[i][j + 1] == 'G' && S[i][j + 2] == 'W');
}
inline bool Vert(int i, int j)
{
    if (M[i][j] || M[i + 1][j] || M[i + 2][j])
        return 0;
    return (S[i][j] == 'R' && S[i + 1][j] == 'G' && S[i + 2][j] == 'W');
}
inline void MakeHorz(int i, int j)
{
    M[i][j] = M[i][j + 1] = M[i][j + 2] = 1;
}
inline void MakeVert(int i, int j)
{
    M[i][j] = M[i + 1][j] = M[i + 2][j] = 1;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++)
        scanf("%s", &S[i]);
    for (int d = 0; d < n + m - 1; d ++)
    {
        int l = max(d - m + 1, 0);
        int r = min(d, n - 1);

        memset(dp, 0, sizeof(dp));
        for (int i = l; i <= r; i ++)
        {
            dp[i][0] = max((i > 0 ? dp[i - 1][0] : 0), (i > 1 ? dp[i - 2][1] : 0));
            if (Horz(i, d - i))
                dp[i][0] = max(dp[i][0], (i > 0 ? dp[i - 1][0] : 0) + 1);
            dp[i][1] = max(dp[i][0], (i > 0 ? dp[i - 1][1] : 0));
            if (Vert(i, d - i))
                dp[i][1] = max(dp[i][1], (i > 0 ? dp[i - 1][1] : 0) + 1);
        }
        cnt += dp[r][1];

        /*for (int i = l; i <= r;)
        {
            int j1 = i, j2 = i;
            while (j1 <= r && Horz(j1, d - j1))
                j1 ++;
            while (j2 <= r && Vert(j2, d - j2))
                j2 ++;
            if (j1 == i && j2 == i)
                {i ++; continue;}
            if (j1 < j2)
            {
                cnt += j2 - i;
                for (int j = i; j < j2; j ++)
                    MakeVert(j, d - j);
                i = j2;
            }
            else
            {
                cnt += j1 - i;
                for (int j = i; j < j1; j ++)
                    MakeHorz(j, d - j);
                i = j1;
            }
        }*/
    }
    return !printf("%d\n", cnt);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:32:26: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[3003]' [-Wformat=]
         scanf("%s", &S[i]);
                     ~~~~~^
dango_maker.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &S[i]);
         ~~~~~^~~~~~~~~~~~~

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