Submission #1248376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248376		clementine	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	526 ms	141596 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int grid[3003][3003];
int dp[3003][3003][3];

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i = 0; i <=3002; i ++)
    {
        for(int j = 0; j <= 3002;j++)
        {
            grid[i][j] = -1;
            dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 0;
        }
    }
    for(int i = 1; i <=n; i ++)
    {
        for(int j = 1; j <=m; j ++)
        {
            char t;
            cin >> t;
            if(t == 'R')
            {
                grid[i][j] = 0;
            }
            else
            {
                t == 'G' ? grid[i][j] = 1 : grid[i][j] = 2;
            }
            //cout << grid[i][j];
        }//cout << '\n';
    }

    for(int i = 2; i <= (n + m); i ++)
    {
        for(int j = max(i-n, 1); j <= min(i - 1, m); j ++)
        {
            //cout << grid[i-j][j];
            //we loop at dp[i - j][j][ 0 == vertical, 1 = horiz, 2 = no dango]
            // if we don't make a dango with this block
            dp[i-j][j][2] = max(max(dp[i-j + 1][j - 1][0], dp[i-j + 1][j - 1][1]) , dp[i-j + 1][j - 1][2]);
            //cout << " dp[2] : " << dp[i-j][j][2] << '\n';
            if(grid[i-j][j] == 1)
            {
                if(grid[i-j-1][j] == 0 && grid[i-j+1][j] == 2)
                {
                    dp[i-j][j][0] = max(dp[i-j + 1][j-1][0], dp[i-j + 1][j-1][2]) + 1;
                    //cout << " dp[0] : " << dp[i-j][j][0] << '\n';
                }
                if(grid[i-j][j-1] == 0 && grid[i-j][j + 1] == 2)
                {   
                    dp[i-j][j][1] = max(dp[i-j + 1][j-1][1], dp[i-j + 1][j-1][2]) + 1;
                    //cout << " dp[1] : " << dp[i-j][j][1] << '\n';
                }
            }
        } //cout << '\n';
    }
    ll ans = 0;
    for(int i = 1; i <=m; i ++)
    {
        ans += max(max(dp[1][i][0], dp[1][i][1]) , dp[1][i][2]);
    }
    for(int i = 2; i <=n; i ++)
    {
        ans += max(max(dp[i][m][0], dp[i][m][1]) , dp[i][m][2]);
    }
    cout << ans;
}

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