Submission #231076

#TimeUsernameProblemLanguageResultExecution timeMemory
231076Andrei_CotorDango Maker (JOI18_dango_maker)C++11
100 / 100
259 ms18168 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...