Bad Hair Day(1)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3250
一列に並んだ数頭のウシについて、背の高さが与えられます。たとえば6頭のウシの背の高さが、以下のようになっているとします。

ウシ1	ウシ2	ウシ3	ウシ4	ウシ5	ウシ6
10	3	7	4	12	2

ウシ1〜6が左から順に並んでいて、すべてのウシは右側を向いているとしたとき、各ウシから見て前のウシの頭(頭頂部)が見えるかどうかと調べて、その頭数の合計を求めてください。

たとえばウシ1の背の高さは10なので、それより背の低いウシ2,3,4の頭を見ることができますが、ウシ5の背の高さは12ですから頭が見えません。ウシ5の頭が見えないということは、いくら背が低くてもその右隣にいるウシ6の頭をみることはできません。このように、ウシ1〜6について頭を見ることが出来るウシの数を調べると、以下のようになります。

ウシの番号	頭が見えるウシの番号	頭数
1	2, 3, 4	3
2	見えない	0
3	4	1
4	見えない	0
5	6	1
6	目の前にウシがいない	0

頭が見えるウシの頭数の合計は、3+1+1=5が正解になります。このような計算を行うプログラムを書いてください。ただし、ウシの頭数は最大80000で背の高さは1000000000までの自然数とします。入力値の書式は、1行目にウシの頭数N、続くN行に背の高さが含まれます。

入力例

6
10
3
7
4
12
2

出力例

5

解答の最大値は、およそ80000*80000/2とsigned intの範囲を超えてしまうので、少し注意が必要です。「それさえ気をつければ簡単じゃーん」と、

#include<stdio.h>

int cow[80000];

unsigned int sum;
int i,j,n;

main(n)
{
  scanf("%d",&n);

  for(i=0;i<n;++i)
    scanf("%d",&cow[i]);

  for(i=0;i<n;++i)
    for(j=i;++j<n&&cow[i]>cow[j];)++sum;

  printf("%u\n",sum);
}

みたいなコードを書いてしまうと、入力のサイズが大きくなった場合にTLEになるでしょうから、頭数をうまくキャッシュして計算量を抑える必要があります。