std::pair<int, int> vs struct with two int's

In an ACM example, I had to build a big table for dynamic programming. I had to store two integers in each cell, so I decided to go for a std::pair<int, int>. However, allocating a huge array of them took 1.5 seconds:

std::pair<int, int> table[1001][1001];

Afterwards, I have changed this code to

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

and the allocation took 0 seconds.

What explains this huge difference in time?