Tic-tac-toe with only crosses as quick as possible As per Luke's request and Peter Taylor's addition to this challenge.
Introduction
Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only going to use crosses. The first person who places three crosses in a row loses. An interesting fact is that the maximum amount of crosses before someone loses, is equal to 6:
X X -
X - X
- X X

That means that for a 3 x 3 board, the maximum amount is 6. So for N = 3, we need to output 6.
Another example, for N = 4, or a 4 x 4 board:
X X - X
X X - X
- - - -
X X - X

This is an optimal solution, you can see that the maximum amount of crosses is equal to 9. An optimal solution for a 12 x 12 board is:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X

This results in 74.
The task
Your task is to compute the results as fast as possible. I will run your code on the test case 13. This will be done 5 times and then the average is taken of the run times. That is your final score. The lower, the better.
Test cases
N     Output
1       1
2       4
3       6
4       9
5       16
6       20
7       26
8       36
9       42
10      52
11      64
12      74
13      86
14      100
15      114

More information can be found at https://oeis.org/A181018.
Rules

This is fastest-code, so the fastest submission wins!
You must provide a full program.
Please also provide how I have to run the program. I am not familiar with all programming languages and how they work, so I need a little bit of help here.
Of course, your code needs to compute the correct result for each test case.

Submissions:

feersum (C++11): 28s
Peter Taylor (Java): 14m 31s
Java, 14m 31s

This is essentially the program which I posted to OEIS after using it to extend the sequence, so it's a good reference for other people to beat. I've tweaked it to take the board size as the first command-line argument.

public class A181018 {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.println(calc(n));
    }

    private static int calc(int n) {
        if (n &lt; 0) throw new IllegalArgumentException("n");
        if (n &lt; 3) return n * n;

        // Dynamic programming approach: given two rows, we can enumerate the possible third row.
        // sc[i + rows.length * j] is the greatest score achievable with a board ending in rows[i], rows[j].
        int[] rows = buildRows(n);
        byte[] sc = new byte[rows.length * rows.length];
        for (int j = 0, k = 0; j &lt; rows.length; j++) {
            int qsc = Integer.bitCount(rows[j]);
            for (int i = 0; i &lt; rows.length; i++) sc[k++] = (byte)(qsc + Integer.bitCount(rows[i]));
        }

        int max = 0;
        for (int h = 2; h &lt; n; h++) {
            byte[] nsc = new byte[rows.length * rows.length];
            for (int i = 0; i &lt; rows.length; i++) {
                int p = rows[i];
                for (int j = 0; j &lt; rows.length; j++) {
                    int q = rows[j];
                    // The rows which follow p,q cannot intersect with a certain mask.
                    int mask = (p &amp; q) | ((p &lt;&lt; 2) &amp; (q &lt;&lt; 1)) | ((p &gt;&gt; 2) &amp; (q &gt;&gt; 1));
                    for (int k = 0; k &lt; rows.length; k++) {
                        int r = rows[k];
                        if ((r &amp; mask) != 0) continue;

                        int pqrsc = (sc[i + rows.length * j] &amp; 0xff) + Integer.bitCount(r);
                        int off = j + rows.length * k;
                        if (pqrsc &gt; nsc[off]) nsc[off] = (byte)pqrsc;
                        if (pqrsc &gt; max) max = pqrsc;
                    }
                }
            }

            sc = nsc;
        }

        return max;
    }

    private static int[] buildRows(int n) {
        // Array length is a tribonacci number.
        int c = 1;
        for (int a = 0, b = 1, i = 0; i &lt; n; i++) c = a + (a = b) + (b = c);

        int[] rows = new int[c];
        int i = 0, j = 1, val;
        while ((val = rows[i]) &lt; (1 &lt;&lt; (n - 1))) {
            if (val &gt; 0) rows[j++] = val * 2;
            if ((val &amp; 3) != 3) rows[j++] = val * 2 + 1;
            i++;
        }

        return rows;
    }
}


Save to A181018.java; compile as javac A181018.java; run as java A181018 13. On my computer it takes about 20 minutes to execute for this input. It would probably be worth parallelising it.