#include <stdio.h>

#ifdef WIN32

#include <windows.h>
double get_time()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}

#else

#include <sys/time.h>
#include <sys/resource.h>

double get_time()
{
    struct timeval t;
    struct timezone tzp;
    gettimeofday(&t, &tzp);
    return t.tv_sec + t.tv_usec*1e-6;
}

#endif

#define HEIGHT 10000
#define WIDTH 10000

typedef int board[HEIGHT + 2][WIDTH + 2];
typedef int board2[(HEIGHT + 2) * (WIDTH + 2)];
typedef char board3[(HEIGHT + 2) * (WIDTH + 2)];

board b;
board2 b2;
board3 b3;

int min(int a, int b)
{
   return (a < b) ? a : b;
}

int max(int a, int b)
{
   return (a > b) ? a : b;
}

static int countNeighbors(board b, int x, int y)
{
   int n = 0;

   int x_left = max(0, x-1);
   int x_right = min(HEIGHT, x+2);
   int y_left = max(0, y-1);
   int y_right = min(WIDTH, y+2);

   int xx, yy;
   for (xx = x_left; xx < x_right; ++xx) {
       for (yy = y_left; yy < y_right; ++yy) {
           n += b[xx][yy];
       }
   }

   return n - b[x][y];
}

int countNeighborsFast(board b, int x, int y)
{
    int n = 0;
    n += b[x-1][y-1];
    n += b[x][y-1];
    n += b[x+1][y-1];
    n += b[x-1][y];
    n += b[x+1][y];
    n += b[x-1][y+1];
    n += b[x][y+1];
    n += b[x+1][y+1];
    return n;
}

int countNeighborsLinear(board2 b, int x, int y)
{
    int n = 0;
    int pos = (WIDTH + 2) * y + x;
    n += b[pos - 1 - (WIDTH + 2)];
    n += b[pos     - (WIDTH + 2)];
    n += b[pos + 1 - (WIDTH + 2)];
    n += b[pos - 1];
    n += b[pos + 1];
    n += b[pos - 1 + (WIDTH + 2)];
    n += b[pos     + (WIDTH + 2)];
    n += b[pos + 1 + (WIDTH + 2)];
    return n;
}

int countNeighborsLinearAndChars(board3 b, int x, int y)
{
    int n = 0;
    int pos = (WIDTH + 2) * y + x;
    n += b[pos - 1 - (WIDTH + 2)];
    n += b[pos     - (WIDTH + 2)];
    n += b[pos + 1 - (WIDTH + 2)];
    n += b[pos - 1];
    n += b[pos + 1];
    n += b[pos - 1 + (WIDTH + 2)];
    n += b[pos     + (WIDTH + 2)];
    n += b[pos + 1 + (WIDTH + 2)];
    return n;
}

int countNeighborsLinearAndCharsAndLinearLoop(board3 b, int pos)
{
    int n = 0;
    n += b[pos - 1 - (WIDTH + 2)];
    n += b[pos     - (WIDTH + 2)];
    n += b[pos + 1 - (WIDTH + 2)];
    n += b[pos - 1];
    n += b[pos + 1];
    n += b[pos - 1 + (WIDTH + 2)];
    n += b[pos     + (WIDTH + 2)];
    n += b[pos + 1 + (WIDTH + 2)];
    return n;
}

int countNeighborsLinearAndCharsAndLinearLoopAndSum(board3 b, int pos)
{
    return
    b[pos - 1 - (WIDTH + 2)] +
    b[pos     - (WIDTH + 2)] +
    b[pos + 1 - (WIDTH + 2)] +
    b[pos - 1] +
    b[pos + 1] +
    b[pos - 1 + (WIDTH + 2)] +
    b[pos     + (WIDTH + 2)] +
    b[pos + 1 + (WIDTH + 2)];
}

int main()
{
   int x, y;
   double start = get_time();
   int sum = 0;

   for (y = 0; y < HEIGHT; y++)
      for (x = 0; x < WIDTH; x++)
         sum += countNeighbors(b, x, y);

   printf("Original: %.2fs\n", get_time() - start);

   start = get_time();

   for (y = 1; y <= HEIGHT; y++)
      for (x = 1; x <= WIDTH; x++)
     sum += countNeighborsFast(b, x, y);

   printf("Mine: %.2fs\n", get_time() - start);

   start = get_time();

   for (y = 1; y <= HEIGHT; y++)
      for (x = 1; x <= WIDTH; x++)
     sum += countNeighborsLinear(b2, x, y);

   printf("Linear: %.2fs\n", get_time() - start);

   start = get_time();

   for (y = 1; y <= HEIGHT; y++)
      for (x = 1; x <= WIDTH; x++)
     sum += countNeighborsLinearAndChars(b3, x, y);

   printf("LinearAndChars: %.2fs\n", get_time() - start);

   start = get_time();

   int i;
   for (i = WIDTH + 3; i <= (WIDTH + 2) * (HEIGHT + 1) - 2; i++)
     sum += countNeighborsLinearAndCharsAndLinearLoop(b3, i);

   printf("LinearAndCharsAndLinearLoop: %.2fs\n", get_time() - start);

   start = get_time();

   for (i = WIDTH + 3; i <= (WIDTH + 2) * (HEIGHT + 1) - 2; i++)
     sum += countNeighborsLinearAndCharsAndLinearLoopAndSum(b3, i);

   printf("LinearAndCharsAndLinearLoopAndSum: %.2fs\n", get_time() - start);

   return sum;
}