牛客小白月赛28 A-牛牛的健身运动

牛牛的健身运动

• 分析

  我也不知道怎么证明，口胡一把吧。先描几个点看看情况，大概就是这个样子

  

• 代码

/*在m天中选一天出来锻炼*/

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2e3+10;

int n,m;ll ans=-2e18;
ll a[N],b[N],c[N];

inline ll ch(ll k)
{
    ll x=2e18,y=2e18;
    if(k>m) return -x-y;

    for (int i=1;i<=n;i++)
        c[i]=k*a[i]+b[i];

    sort(c+1,c+n+1);
    ans=max(ans,c[1]+c[2]);
    return c[1]+c[2];
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]);

    ll l=1,r=m;
    while(l<=r)
    {
        ll lm=l+(r-l)/3,rm=r-(r-l)/3;
        if(ch(lm)>ch(rm)) r=rm-1;
        else l=lm+1;
    }

    printf("%lld\n",ans);

    return 0;
}