简要题意

给若干物品，按一定顺序选取物品。每个物品有一个限制值：如果当前选取物品的体积没有超过该值，则物品的体积乘上一个定值。询问最大可能总体积。

分析

首先，我们可以把任务分为 “好任务”（可以获得倍增器的任务）和 “普通任务”（不能获得倍增器的任务）。

那么我们观察到：一定存在一个任务顺序，使得我们先做好任务，再做普通任务。

证明：如果存在一个两个任务 $i,j$，且 $i$ 是普通任务，$j$ 是好任务，且 $i$ 先于 $j$ 做,我们设当前经验为 $xp$。那么有 $xp \ge vd_i,xp+x_i\le vd_j-1$；如果我们交换 $i$ 和 $j$ 的顺序，那么有 $xp \le vd_j-1，xp+cx_j\ge vd_i$。两个任务性质不变，因此交换不会变劣。

其次，我们再观察到：普通任务的顺序不影响最后经验值。

因为顺序只关系我们能否获得增幅器，既然已经不能获得增幅器了，那么顺序也就没有意义了。

最后，我们有一个惊人注意力：我们定义 $mx_i=vd_i+cx_i-1$，即做完任务 $i$ 时可能的最大经验值，那么我们会优先做 $mx_i$ 小的好任务。

证明：

我们假设存在两个好任务 $i,j$，$i$ 先于 $j$ 做且 $mx_i>mx_j$，那么可以推断：

$$\begin{cases} xp \le xd_i-1\\ xp+cx_i \le vd_j-1\\ xp \le vd_j-1\\ vd_j+cx_j-1\le vd_i+cx_i-1 \end{cases}$$

那么我们要判断 $xp+cx_j$ 和 $vd_i-1$ 的大小关系，注意到：

$$vd_i-1 \ge vd_j+cx_j-cx_i\ge xp+cx_i+cx_j-cx_i+1 \ge xp+cx_j$$

因此交换 $i$ 和 $j$ 的顺序不会改变任务的性质，不会使答案变劣。

根据上述性质，我们按照 $mx_i$ 给任务升序排序，那么依照这个顺序 dp 即可。

这个 dp 类似于背包，我们定义 $f_{i,j}$ 为考虑到第 $i$ 个物品，是否可以使从任务获得的经验为 $j$。转移时钦定当前物品是否在好物品集合中，这是简单的。找答案就倒序枚举 dp 数组，找到一个可以的经验值。

我们定义 $m=nc \times\sum x_i$时间复杂度为 $O(nm+n\log n)$，接近 $1.6 \times 10^{13}$，非常不可过。

考虑优化：

• 我们可以把好任务获得的经验分成 $x_i$ 和 $(c-1)x_i$，这样我们就可以只统计后面那部分的贡献。换句话说，我们可以只关心好任务的选取情况；
• 因为所有好任务提供的经验的都有 $c-1$ 的系数，将其提出，可以降低值域大小；
• $01$ 背包可以使用 bitset 优化；

经过上述优化后，我们定义 $m=n\times \sum x_i$，时间复杂度为 $O(\dfrac{nm+m \log m}{w})$。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf (1ll<<60)
#define For(i,s,t) for(int i=s;i<=t;++i)
#define Down(i,s,t) for(int i=s;i>=t;--i)
#define ls (i<<1)
#define rs (i<<1|1)
#define bmod(x) ((x)>=p?(x)-p:(x))
#define lowbit(x) ((x)&(-(x)))
#define End {printf("NO\n");exit(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline void ckmx(int &x,int y){x=(x>y)?x:y;}
inline void ckmn(int &x,int y){x=(x<y)?x:y;}
inline void ckmx(ll &x,ll y){x=(x>y)?x:y;}
inline void ckmn(ll &x,ll y){x=(x<y)?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline ll max(ll x,ll y){return x>y?x:y;}
char buf[1<<20],*p1,*p2;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({\
    int x = 0, f = 1;\
    char c = gc();\
    while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();\
    while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc();\
    f * x;\
})
void write(int x){
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}
const int N=2005,M=4e6+4;
int n,v,c,m=4e6+4;
struct Node{int x,d,mx,id;}a[N];
bool cmp(Node x,Node y){return x.mx<y.mx;}
bitset<M> f,large,g;
int main()
{
    n=read(),v=read(),c=read();
    For(i,1,n){
        a[i].x=read(),a[i].d=read();
        a[i].mx=c*a[i].x+v*a[i].d-1,a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    f.set(0),large.set(0);
    int pw=1;
    while(pw<m) large|=(large<<pw),pw<<=1;
    int num=0,lim;
    For(i,1,n){
        num+=a[i].x,lim=min(num,(a[i].d*v-1)/c);
        g=(large>>(m-lim-1));
        g=(f&g);
        g=(g<<a[i].x);
        f=(f|g);
    }
    Down(i,num,0)
        if(f[i]){
            ll val=1ll*(c-1)*i+num;
            printf("%lld",val);
            break;
        }
    return 0;
}