I have use a O(n^2/31) dynamic programming approach and use bitset optimization and get AC 0.06s..

1873447 09:40:10 Scenery Accepted 0.06 s C++

here is my code:

algorithm correctness have not been proved yet,

http://ideone.com/g5otEq