小学生放假了

总时限	26s	内存限制	256MB
出题人		提交情况	16/150
初始分值	1500	锁定情况

背景

我们能见到的最可怕的事情，莫过于小学生放假了！

描述

小学生要放假了！MT学校一共有N个小学生，学校旁边的ET小卖部希望在小学生放假之前做好坑蒙小学生的准备！ET小卖部一共有M个不同的商品，每个商品的价格可以定位任意非负整数，每个商品的数量是无限的。每个小学生有Ci RMB，每人只能购买一个商品，他们希望他们购买的商品尽量贵。小卖部应该如何设定每个商品的价格，使得他们坑蒙小学生的收入尽可能多呢？请输出最多的收入。

输入格式

第一行两个用空格隔开的整数N，M。

紧接着N行，第i+1行一个整数，表示Ci（见题目描述）

输出格式

一个整数，表示最多的收入。

样例输入

5 313579

样例输出

22

样例解释

三个商品的价格分别设置为3RMB，7RMB和9RMB。

第一个小学生由于没有足够的RMB，不购买任何商品；

第二个小学生和第三个小学生只能购买3RMB的商品；

第四个小学生可以购买7RMB的商品；

第五个小学生可以购买9RMB的商品。

3 + 3 + 7 + 9 = 22，所以这种方案获得了22RMB的收入。

可以证明，没有更优的方案。

数据范围与约定

对于100%的数据，1 <= Ci <= 10⁹，1 <= N <= 10000，1 <= M <= 2000。

单点时间限制2s。

来源

原创

 

 

斜率优化易错点。。。

1.不等式*(-1),2边都要变号。

2.注意叉积乘爆，切忌bool强转 (bool) t >0

                                                         优先级高

3.初值P(0,a[1],0)

4.eps乱用

5.a.y-b.y

   a.x=b.x的情况  *inf 注意+,-

    否则long double 可能出现真的正负无穷   然后T得惨惨的，还查不出错。。。

     能出正解的其实，上面。。。↑ 

写了一天各种错。。无语了。。后天考试。。考文化。。。坐等爆0。。。。

顺便说一下clock()的用法

clock()/CLOCKS_PER_SEC 返回程序运行开始到执行的时间(单位:s)

卡时间专用。。

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i
             
              =0;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (100000007)#define MAXN (10000+10)#define MAXM (2000+10)#define eps 1e-13#define Read(x) { \ while (!isdigit(c=getchar())); \ x=c-48; \ while (isdigit(c=getchar())) x=x*10+c-48; \ }long long mul(long long a,long long b){return (a*b)%F;}long long add(long long a,long long b){return (a+b)%F;}long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}typedef long long ll;int n,m;char c;ll a[MAXN];ll f[MAXM][MAXN]={0},T[MAXN]={0},h[MAXN];struct P{ int i; long double x,y; P(int _i,ll _x,ll _y):i(_i),x(_x),y(_y){} P(ll _x,ll _y):x(_x),y(_y){} P(){} friend long double kk(P a,P b){if (abs(a.x-b.x)
              
               eps;} friend long double operator*(V a,V b){/*cout<
               
                <
                
                 =-j) head++; // cout<
                 
                  <<' '<<-j<
                  
                   =0) tail--; st[++tail]=A; // } } } //ll ans=0; /* For(i,m) { For(j,n) ans=max(ans,f[i][j]);//,cout<
                   
                    <<' ';cout<