Cod sursă (job #755950)

#include <fstream>

using namespace std;

ifstream cin ( "2sah.in" ) ;
ofstream cout ( "2sah.out" ) ;

int mat [ 50000001 ] [ 2 ] ;

int main()
{
      int cerinta , n , k ;
      cin >> cerinta ;
      cin >> n >> k ;
      mat [ n ] [ 0 ] = 1 ;

      int sum = 0 ;
      if ( cerinta == 1 ) {
         for ( int i = 0 ; i < k - 1 ; i ++ ) {
            for ( int j = n - i - 1 ; j < n ; j ++ ) {
               mat [ j ] [ ( i + 1 ) % 2 ] = mat [ j - 1 ] [ i % 2 ] + mat [ j ] [ i % 2 ] + mat [ j + 1 ] [ i % 2 ] ;
               mat [ j ] [ ( i + 1 ) % 2 ] = mat [ j ] [ ( i + 1 )% 2 ] % 100003 ;
            }
            mat [ n ] [ ( i + 1 ) % 2 ] = ( mat [ n - 1 ] [ i % 2 ] * 2 + mat [ n ] [ i % 2 ] ) % 100003 ;
            if ( i == k - 2 ) {
               for ( int j = n - i - 1 ; j < n ; j ++ ) {
                  sum = sum + mat [ j ] [ ( i + 1 ) % 2 ] * 2 ;
                  sum = sum  % 100003 ;
               }
               sum += mat [ n ] [ ( i + 1 ) % 2 ] ;
               sum = sum  % 100003 ;
            }
          }

      }
      else
      {
         k += 2 ;
         for ( int i = 0 ; i < n ; i ++ ) {
            for ( int j = n - i - 1 ; j < n ; j ++ ) {
               mat [ j ] [ ( i + 1 ) % 2 ] = mat [ j - 1 ] [ i % 2 ] + mat [ j ] [ i % 2 ] + mat [ j + 1 ] [ i % 2 ] ;
               mat [ j ] [ ( i + 1 ) % 2 ] = mat [ j ] [ ( i + 1 )% 2 ] % 100003 ;
            }
            mat [ n ] [ ( i + 1 ) % 2 ] = ( mat [ n - 1 ] [ i % 2 ] * 2 + mat [ n ] [ i % 2 ] ) % 100003 ;
            if ( k <= n ){
               sum += mat [ k - 1 ] [ ( i + 1 ) % 2 ] ;
               sum = sum % 100003 ;
               k += 2 ;
            }
            else
               if ( k <= 2*n + 1 ) {
                  sum += mat [ k - n - 1 ] [ ( i + 1 ) % 2 ] ;
                  sum = sum % 100003 ;
                  k += 2 ;
               }
          }
      }
      cout << sum ;
      return 0;
}