autostrada1

#include <stdio.h>

#define MAXN 2000

int dl[] = { -1, 0, 1, 0 }, dc[] = { 0, 1, 0, -1 };

short drum[2][1 + MAXN][1 + MAXN]; // 0 daca am drum catre sud, 1 catre est
int cost[5];

int main() {
  FILE *fin, *fout;
  int n, i, l, c, lnou, cnou, lmin, cmin, k, d, p, dir, total;

  fin = fopen( "autostrada.in", "r" );
  fscanf( fin, "%d%d%d%d", &n, &k, &l, &c );
  fscanf( fin, "%d%d%d", &cost[2], &cost[3], &cost[4] );
  cost[1] = cost[2]; // cumva costul e acelasi, desi e doar jumate :-)

  // marcam segmentele de drum in matrice
  i = 0;
  while ( i < k && l > 0 && l <= n && c > 0 && c <= n ) {
    fscanf( fin, "%d%d", &dir, &p );
    lnou = l + dl[dir] * p;
    cnou = c + dc[dir] * p;
    if ( lnou > 0 && lnou <= n && cnou > 0 && cnou <= n ) {
      lmin = l < lnou ? l : lnou;
      cmin = c < cnou ? c : cnou;
      if ( drum[dir % 2][lmin][cmin] < p )
        drum[dir % 2][lmin][cmin] = p;
    }
    l = lnou;
    c = cnou;
    i++;
  }
  fclose( fin );

  fout = fopen( "autostrada.out", "w" );
  if ( i < k )
    fprintf( fout, "TRASEU INVALID\n%d\n", i );
  else {
    // calculam drumurile verticale in matrice
    for ( c = 1; c <= n; c++ ) {
      d = 0;
      for ( l = 1; l <= n; l++ ) {
        if ( drum[0][l][c] > d )
          d = drum[0][l][c];
        if ( d > 0 ) {
          drum[0][l][c] = 1;
          d--;
        }
      }
    }

    // calculam drumurile orizontale in matrice si insumam costul
    total = 0;
    for ( l = 1; l <= n; l++ ) {
      d = 0;
      for ( c = 1; c <= n; c++ ) {
        if ( drum[1][l][c] > d )
          d = drum[1][l][c];
        if ( d > 0 ) {
          drum[1][l][c] = 1;
          d--;
        }
        total += cost[drum[0][l - 1][c] + drum[1][l][c]
                      + drum[0][l][c] + drum[1][l][c - 1]];
      }
    }
    fprintf( fout, "TRASEU VALID\n%d\n", total );
  }
  fclose( fout );

  return 0;
}