Możliwe, że PYTHON jest za wolny jak na tak duże dane wejściowe. Bo właśnie wczytywanie jest zazwyczaj wąskim gardłem.
Poszukaj informacji jak przyśpieszyć czytanie ze standardowego wejścia w PYTHON’ie, np. sys.stdin.readline( )
.
Na razie nikt nie rozwiązał tego zadania w tym języku, więc nie będzie łatwo.