Supermarket

http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
スーパーで売り出す商品の、利益と売り出し可能な期間が与えられます。たとえば、

4  50 2  10 1   20 2   30 1

のようなデータなら、4種類の商品で1つ目の商品は利益が50、売り出す期間が（単位を時間とすれば）2時間です。1時間に1つだけ商品を出すとすれば、最初の1時間に利益30の商品、次の1時間に利益50の商品を売り出すと合計の利益は80になります。

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10

のような入力なら、1時間ごとに利益が20,100,10,50,5の商品を売り出せば、利益の合計は185になります。このように、期間内の売り上げが最大になるように売り出すスケジュールを考えて、その売り上げ合計を答えてください。

売り出し可能な期間が同じもので利益を比較しながら合計すると、たとえば

5 1
8 1
30 2
40 2

のような入力の場合、正しくは30,40と売り出して70が最大であるのに、8,40を選んで48と答えてしまうミスが考えられるので注意が必要でしょう。

int s['~~'],v['~~'];

p(int*a,int*b){return*a>*b?-1:*a<*b;}

main(i,n,t,m)
{
  for(;~scanf("%d",&n);printf("%d\n",m))
  {
    for(i=0;i<n*2;)v[i]=scanf("%d",s+i++);
    qsort(s,n,8,p);
    for(m=i=0;i<n;i++)
      for(t=s[i-~i];v[t]?v[t]=!(m+=s[i*2]):--t;);
  }
}

あと、結構大きな値も含まれているようなのでオーバーフローを防ぐコードにしておかなければならない。割と普通に書いて普通に短縮した感じです。