朴素的做法显然是O(n3)的

考虑优化，我们将约束条件变形为A*h+B*v<=A*minh+B*minv+c

右边是一个定值，当右边确定了minh之后，随着minv的增大，原来满足条件的且v>=minv的一定还满足条件

然后我们只要先对A*h+B*v排序，然后穷举minh，然后扫一遍即可

O(n2)的算法很显然，我正好卡着时限过去的……

但这道题的本意肯定是有O(nlogn)的算法，求教导

1 type node=record 2        h,v,s:longint; 3      end; 4  5 var f,v:array[0..10010] of longint; 6     h:array[0..10010] of boolean; 7     w:array[0..5010] of node; 8     ans,t,m,x,y,n,i,j,sum,s,a,b,c,k:longint; 9 10 procedure swap(var a,b:node);11   var c:node;12   begin13     c:=a;14     a:=b;15     b:=c;16   end;17 18 procedure sort(l,r: longint);19   var i,j,x: longint;20   begin21     i:=l;22     j:=r;23     x:=w[(l+r) div 2].s;24     repeat25       while w[i].s
      
       j) then28       begin29         swap(w[i],w[j]);30         inc(i);31         j:=j-1;32       end;33     until i>j;34     if l
       
        m then m:=x;45     v[y]:=1;46     w[i].h:=x;47     w[i].v:=y;48     w[i].s:=a*x+b*y;49   end;50   sort(1,n);51   for i:=1 to 10000 do52     if v[i]=1 then53     begin54       inc(t);55       f[t]:=i;  //表示v可能的数字56     end;57 58   for i:=1 to m do59   begin60     if not h[i] then continue;  //穷举minh61     fillchar(v,sizeof(v),0);62     sum:=0;63     k:=1;64     for j:=1 to t do65     begin66       if j<>1 then67         sum:=sum-v[f[j-1]]; //对于当前minv，小于的不算68       s:=a*i+b*f[j]+c;69       while (k<=n) and (w[k].s<=s) do70       begin71         if (w[k].h>=i) and (w[k].v>=f[j]) then72         begin73           inc(sum);74           inc(v[w[k].v]);  //方便随着minv的增大，快速减去小于minv的数目75         end;76         inc(k);77       end;78       if sum>ans then ans:=sum;79       if k>n then break; //后面一定只减不增80     end;81   end;82   writeln(ans);83 end.