is there O(N^2) solution???
I have used at least three approach to solve this problem.first two get TLE, last one AC 50 ms(the time is surprising me,because I use O(n^3) precal +constant optimizition..
the second one I use O(n^2)precal +O(n^2*log(n)) FFT obviously it will TLE because there are 1500 test cases..
the third one I use O(n^3) dp[i][j][s] record to fill first i empty cells,there are j numbers which is smaller than a1 and s numbers bigger than a(i+1) and ai<a(i+1) dp[i][j][s] means ai>a(i+1). in order to get O(1)transfer we can recodrd sum[i][j][s]..
to speed up the process of O(N^3) we only need to record states that is visit by the input,so I sort the input increasing by n use scroll array. use f record f[n][a1-1]=max(f[n][a1-1],n-an)
for(i=1998;i>=0;i--) for(j=i;j>=0;j--) f[i][j]=max(f[i][j],f[i+1][j]-1);
for each first two state (i,j) the third state that visit is only [0,min(i-j,f[i][j])], this speed up made my code 50ms..