Submission #898115

#	Time	Username	Problem	Language	Result	Execution time	Memory
898115		andrei_iorgulescu	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	243 ms	68176 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

int n,m;
char a[3005][3005];
int dp[3005][3];
vector<int>v[6005];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j],v[i + j].push_back(i);
    int ans = 0;
    for (int d = 2; d <= n + m; d++)
    {
        for (int i = 0; i < v[d].size(); i++)
        {
            dp[i][0] = dp[i][1] = dp[i][2] = 0;
            if (i == 0)
            {
                int l = v[d][i],c = d - l;
                if (c - 1 > 0 and c + 1 <= m and a[l][c - 1] == 'R' and a[l][c] == 'G' and a[l][c + 1] == 'W')
                    dp[i][1] = 1;
                if (l - 1 > 0 and l + 1 <= n and a[l - 1][c] == 'R' and a[l][c] == 'G' and a[l + 1][c] == 'W')
                    dp[i][2] = 1;
            }
            else
            {
                int l = v[d][i],c = d - l;
                dp[i][0] = max(dp[i - 1][0],max(dp[i - 1][1],dp[i - 1][2]));
                ///var 0: nu pun centrat in (l,c)
                ///var 1: pun orizontal centrat in (l,c)
                ///var 2: pun vertical centrat in (l,c)
                if (c - 1 > 0 and c + 1 <= m and a[l][c - 1] == 'R' and a[l][c] == 'G' and a[l][c + 1] == 'W')
                    dp[i][1] = max(dp[i - 1][0],dp[i - 1][1]) + 1;
                if (l - 1 > 0 and l + 1 <= n and a[l - 1][c] == 'R' and a[l][c] == 'G' and a[l + 1][c] == 'W')
                    dp[i][2] = max(dp[i - 1][0],dp[i - 1][2]) + 1;
            }
        }
        int sz = v[d].size() - 1;
        //cout << d << ' ' << max(dp[sz][0],max(dp[sz][1],dp[sz][2])) << endl;
        ans += max(dp[sz][0],max(dp[sz][1],dp[sz][2]));
    }
    cout << ans;
    return 0;
}
/*
4 3
WRW
RGW
GWW
WWW
*/

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int i = 0; i < v[d].size(); i++)
      |                         ~~^~~~~~~~~~~~~

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