Codeforces

Luogu

分析

二分答案，则我们需要判定是否能够让所有竹子的高度 $\leq mid$。

由于竹子的高度不能小于 $0$，所以正着做不太好做；考虑反过来做，即每根竹子初始高度为 $mid$，每天会变矮 $a_i$，你每天可以选 $k$ 根竹子让他们变长 $p$，判断最后所有竹子的高度是否能 $\geq h_i$，且操作过程中竹子的高度不能 $<0$。

考虑贪心，每次选出不增高时高度最快变为 $0$ 的 $k$ 个竹子拔高即可。实现时可以用堆维护所有 $m$ 天后高度 $<h_i$ 的竹子，内部以变为 $0$ 的天数为关键字。那么最后只需要判堆是否为空即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,k,p,a[N],h[N],cnt[N];

struct node { ll d; int id; };
bool operator <(node a,node b) { return a.d>b.d; }
priority_queue<node> Q;

inline int check(ll mid) {
    while (!Q.empty()) Q.pop();
    memset(cnt,0,sizeof(cnt));
    for (re int i=1;i<=n;++i)
        if (mid-1ll*m*a[i]<h[i]) Q.push((node){mid/a[i],i});
    for (re int i=1;i<=m&&!Q.empty();++i) {
        for (re int j=1;j<=k&&!Q.empty();++j) {
            node x=Q.top(); Q.pop();
            if (x.d<i) return 0;
            ++cnt[x.id];
            if (mid-1ll*m*a[x.id]+1ll*p*cnt[x.id]<h[x.id])
                Q.push((node){(mid+1ll*p*cnt[x.id])/a[x.id],x.id});
        }
    }
    return Q.empty();
}

int main() {
    n=read(),m=read(),k=read(),p=read();
    for (re int i=1;i<=n;++i) h[i]=read(),a[i]=read();
    ll L=1,R=1e13;
    while (L<R) {
        ll mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%lld\n",L);
    return 0;
}