http://codeforces.com/problemset/problem/362/C
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 5000 + 5; 6 const int INF = 1<<30; 7 int a[maxn], sum[maxn][maxn], sum2[maxn][maxn]; 8 int main() { 9 int n; 10 scanf("%d", &n); 11 for(int i = 0;i < n; i++) 12 scanf("%d", &a[i]); 13 for(int i = 0;i < n; i++) { 14 sum[i][i] = 0; 15 for(int j = i+1;j < n; j++) { 16 sum[i][j] = sum[i][j-1]; 17 if(a[j] < a[i]) 18 sum[i][j]++; 19 } 20 sum2[i][i] = 0; 21 for(int j = i-1;j >= 0; j--) { 22 sum2[i][j] = sum2[i][j+1]; 23 if(a[i] > a[j]) 24 sum2[i][j]++; 25 } 26 } 27 int tot = 0; 28 for(int i = 0;i < n; i++) { 29 for(int j = i+1;j < n; j++) if(a[i] > a[j]) 30 tot++; 31 } 32 int mn = INF, ans = 0; 33 for(int i = 0;i < n; i++) { 34 for(int j = i+1;j < n; j++) { 35 int cur = tot + (j-i) - 2*sum[i][j-1] + 2*sum2[j][i+1] - (j-i); 36 if(a[i] > a[j]) cur--; 37 else cur++; 38 if(cur < mn) { 39 mn = cur; ans = 1; 40 } 41 else if(cur == mn) ans++; 42 } 43 } 44 printf("%d %d ", mn, ans); 45 return 0; 46 }