Submission #231076

#	Time	Username	Problem	Language	Result	Execution time	Memory
231076		Andrei_Cotor	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	259 ms	18168 KiB

dango_maker

#include<iostream>
#include<algorithm>

using namespace std;

char A[3005][3005];
int Dp[2][3005]; //0-orizontal, 1-vertical

int getval(int diag, int n, int m)
{
    for(int i=1; i<=n+3; i++)
        Dp[0][i]=Dp[1][i]=0;

    int x,y;
    if(diag<=m)
    {
        x=1;
        y=diag;
    }
    else
    {
        x=diag-m+1;
        y=m;
    }

    int nr=0;
    for(int i=1; ; i++)
    {
        if(x>n || y<1)
            break;

        nr++;
        Dp[0][i]=max(Dp[0][i],Dp[0][i-1]);
        Dp[1][i]=max(Dp[1][i],Dp[1][i-1]);

        if(A[x][y]=='R' && A[x][y+1]=='G' && A[x][y+2]=='W')
            Dp[0][i]=max(Dp[0][i],max(Dp[0][i-1],Dp[1][max(0,i-3)])+1);

        if(A[x][y]=='R' && A[x+1][y]=='G' && A[x+2][y]=='W')
            Dp[1][i]=max(Dp[1][i],max(Dp[0][i-1],Dp[1][i-1])+1);

        x++;
        y--;
    }

    return max(Dp[0][nr],Dp[1][nr]);
}

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

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

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

    int rez=0;
    for(int i=1; i<=m+n-1; i++) //nu se pot suprapune 2 dango care incep pe diag diferite pt ca trb sa inceapa cu R si cel de pe coloana precedenta ar fi avut G aici
        rez=rez+getval(i,n,m);

    cout<<rez<<"\n";
    return 0;
}

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