Cod sursa(job #3211117)

Utilizator pascarualexPascaru Alexandru pascarualex Data 8 martie 2024 16:25:13
Problema Sortare prin comparare Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.12 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("turcane.in");
ofstream fout("turcane.out");


long long c ;
long long n , m ;
long long p , t , r ;

long long l [ 1005 ] [ 1005  ];
long long col [ 1005 ] [ 1005 ] ;
long long diag [ 1005 ] [ 1005 ];
long long mod = 1000000007;

long long viz [ 1005 ] [ 1005 ];
long long dp [ 1005 ] [ 1005 ];
void lee()
{

    for ( int i = 1; i <= n ; i ++ )
    {
        for ( int j = 1 ; j <=m ; j ++ )
            viz [ i ] [ j ] = 1e9;
    }
    viz [ 1 ]  [ 1 ] = 1;

    for ( long long i = 1; i <= n ; i ++ )
    {

        for ( long long j = 1; j <= m ; j ++ )
        {

            viz [ i  ] [ j ] = min( viz [ max ( 1LL , i - t )] [ j ] + 1 , viz [ i ] [ j ]);
            viz [ i ] [ j ] = min ( viz [ i ] [ max ( 1LL , j - p )] + 1, viz [ i ] [ j ] ) ;

            if ( i - 1 >= 1 && j - 2 >= 1  )
            {
                viz [ i ] [ j ] = min ( viz [ i ] [ j ] , viz [ i - 1 ] [ j - 2 ] + 1) ;
            }

            if ( i - 2 >= 1 && j - 1 >= 1 )
                viz [ i ] [ j ] = min ( viz [ i ] [ j ] , viz [ i - 2 ] [ j - 1 ] + 1) ;

            long long w = min ( i - 1 , r ) ;
            long long y = min ( j - 1 , r ) ;

            w = min ( w , y );
            viz [ i ] [ j ] = min ( viz [ i ] [ j ] , viz [ i - w ] [ j - w ] + 1);
        }
    }
}

int main()
{
    fin >> c ;
    fin >> n >> m ;
    fin >> p >> t >> r ;

    if ( c == 1 )
    {

        lee (  ) ;
        fout << viz [ n ] [ m] - 1 ;
    }
    else
    {
        dp [ 1 ] [ 1 ] = 1;
        col [ 1 ] [ 1 ] = 1;
        l [ 1 ] [ 1 ] = 1 ;
        diag [ 1 ] [ 1 ] = 1 ;
        for ( long long  i = 1; i <= n ; i ++  )
        {
            for ( long long j = 1; j <= m ; j ++ )
            {

                if ( i == 1 && j == 1 )
                    j ++ ;
                long long u = 0 ;

                dp [ i ][ j ] %= mod ;
                dp [ i ] [ j ] += (l [ i - 1 ] [ j ] - l [ max((i - t - 1),u) ] [ j ]) % mod   ;
                dp [ i ] [ j ] %= mod ;
                dp [ i ] [ j ] += (diag [ i - 1 ] [ j - 1 ] - diag [ max ( (i - r - 1) , u)] [ max ( (j - r - 1) , u) ]) % mod  ;
                dp [ i ] [ j ] %= mod ;

                dp [ i ] [ j ] += (col [ i ] [ j - 1 ] - col [ i ] [ max ( (j - p - 1) , u ) ] ) % mod ;
                dp [ i ][ j ] %= mod ;

                if ( i - 1 >= 1 && j - 2 >= 1  )
                {

                    dp [ i ] [ j ] += dp [ i - 1 ] [ j - 2 ] ;
                    dp [ i ] [ j ] %= mod ;
                }

                dp [ i ][ j ] %= mod ;
                if ( i - 2 >= 1 && j - 1 >= 1  )
                {

                    dp [ i ] [ j ] += dp [ i - 2 ] [ j - 1 ];
                    dp [ i ] [ j ] %= mod ;
                }
                dp [ i ][ j ] %= mod ;

                col [ i ] [ j ] = (dp [ i ] [ j ] + col [ i ] [ j - 1 ]);
                l [ i ] [ j ] = (dp [ i ] [ j ] + l [ i - 1 ] [ j ])  ;
                diag [ i ] [j ] = (dp [ i ] [ j ] + diag [ i - 1 ] [ j - 1 ]) ;

                dp [ i ] [ j ] %= mod ;




            }


        }

        fout << dp [ n ] [ m ] % mod  ;

    }

    return 0;
}