RT。

我的思路：

二分 $w$。

对于每一天，因为花费 $p_i$ 获得 $a_i$ 效率或者花费 $q_i$ 获得 $b_i$ 效率，那么只需要求最小代价即可。

显然获得 $a_i\times b_i$ 的最小代价不是 $a_i\times q_i$ 就是 $b_i\times p_i$。

所以就可以通过 $\bmod$ 操作将二分的 $w$ 化为 $1\times 10^4$ 量级，记为 $w_2$。

考虑到有时选溢出 $w_2$ 效率反而更优，但至多不会超过 $w_2+\max(a_i,b_i)$，仍然在 $1\times 10^4$ 量级。

所以在二分前对每一天进行恰好装满完全背包，代价为 $a_i/b_i$，收益为 $p_i/q_i$。

二分时直接查表。

复杂度 $\operatorname{O}(n\times a_i\times b_i+n\cdot(a_i+b_i)\log T)$。其中 $T$ 为最大答案。

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define int long long
//#define double long double
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
#define pb push_back
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
void IOS() {
	ios::sync_with_stdio(false);
	cin.tie(0);
}
void Document() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
}
inline int read(){
	int s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48);ch=getchar();}
	return s*w;
}
inline void write(int x){
	if(x<0){putchar('-');x=-x;}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
void Tell() {
	//写数据结构注意初始化！
	//浮点数类题目过不了优先考虑精度！
	//vector动态开点注意内存重分配！
	//有本地写freopen！没本地别写！！！
	//最后几分钟给我老老实实坐那里，别手贱！！！
	//long long 级别的常数运算一定要用 xll！！！
	//一定要手玩几组极限数据，防止爆数。
	//大数据关同步流！ 大数据关同步流！ 大数据关同步流！
	//删调试！删调试！删调试！删调试！删调试！
	//注意数据类型！注意数据类型！注意数据类型！不要把存 int 的数组开成 char 类型！
	//注意数组大小的上界，不要把 5e6 打成 6e5！
}
const int N=110;
int n,X,a[N],p[N],b[N],q[N],dp[N][N*N+N],l,r,ans,w[2][N],v[2][N];
bool check(int mid) {
	int nw=X;
	FOR(i,1,n) {
		int cnt=mid/(a[i]*b[i]),lst=mid%(a[i]*b[i]);
		int res=1e18;
		FOR(j,0,max(a[i],b[i])) cmin(res,dp[i][lst+j]);
		nw-=(min(p[i]*b[i]*cnt,q[i]*a[i]*cnt)+res);
	}
	return nw>=0;
}
main() {
	cin>>n>>X;
	FOR(i,1,n) {
		cin>>a[i]>>p[i]>>b[i]>>q[i];
		w[0][i]=a[i],w[1][i]=b[i];
		v[0][i]=p[i],v[1][i]=q[i];
	}
	memset(dp,0x3f,sizeof dp);
	FOR(I,1,n) {
		dp[I][0]=0;
		FOR(i,0,1) FOR(j,w[i][I],a[I]*b[I]+max(a[I],b[I])) 
			dp[I][j]=min(dp[I][j],dp[I][j-w[i][I]]+v[i][I]);
	}
	l=0,r=1e9;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) {
			l=mid+1;
			ans=mid;
		} else r=mid-1;
	}
	cout<<ans<<"\n";
	return 0;
}

但是 Atcoder WA了 $12$ 个点。

上述思路是否正确？