My AC solution runs about 10 seconds for test case 1, 2, ...., 2000 on my laptop (it's an old one, though, maybe that's the reason).