感谢 lby奆奆 的指导。
思路：
首先，\(1\) 号的票肯定是越多越好，因此 \(a_1,a_n\) 一定都是投给 \(1\) 号。
我们考虑二分 \(1\) 号能获得的席位数 \(x\)。
显然，对于所有 \(\frac{v_i}{s}>\frac{v_1}{x}\)，它们都会占有一个席位（这里的 \(v_i\) 表示 \(i\) 最后的得票数）。
那问题就转化为求 \(>\frac{v_1}{x}\) 的最小个数，并判断最小个数是否 \(\le m-x\)。
我们考虑设计状态：\(f_{i,j}\) 表示 \(i\) 号从 \(a_i\) 获得了 \(j\) 票（注意只是 \(a_i\)，而不是总票数）。
因此有转移：
\[f_{i,j+(a_{i-1}-k)}=\min\{f_{i-1,k}+\lfloor\frac{x(j+a_{i-1}-k)}{v_1}\rfloor\} \]这里的 \(a_{i-1}-k\) 就是前一个群众剩下的票。
但这样的时间复杂度是 \(nt^2\log m\) 的（\(t\) 表示值域）。
那我们能不能将票数和席位交换一下呢？
考虑重新设计状态：\(f_{i,j}\) 表示 \(s\sim i\) 一共取得 \(j\) 个席位，\(i\) 号需要在 \(a_i\) 最多拿多少票。
现在的判断就变成：是否存在某个 \(f_{n,j}\) 被转移到。
为什么是正确的呢？感性理解一下，我在保证 \(i\) 号最多只能取 \(j\) 个席位的情况下，那么我在 \(a_i\) 多拿一些，\(i+1\) 号在 \(a_i\) 就少拿一些，那么 \(i+1\) 能拿到的席位就变少了。
考虑这时候的转移：设 \(cnt\) 为满足 \(\frac{v_i}{j+1}\le\frac{v_1}{x}<\frac{v_i}{j}\) 的最大 \(v_i\)
因此有 \(cnt=\lfloor\frac{v_1(j+1)}{x}\rfloor\)，且 \(cnt\times x>v_1\times j\) 时在有转移：
\[f_{i, j+k}=\max\{cnt - (a_{i - 1} - f_{i-1,k}) - v_i\} \]时间复杂度为 \(O(nm\log m)\)
代码
#include<bits/stdc++.h>
#define LL long long
#define max(x...) std::max({x})
#define min(x...) std::min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
int n, m, v[55], a[55];
LL f[55][505];
inline bool chk(int x)
{
memset(f, -1, sizeof(f));
FOR(i, 0, m - x)
{
LL L = 1ll * v[1] * i, R = 1ll * v[1] * (i + 1), cnt = R / x;
if(!i) L = -1;
if(cnt * x > L)
f[2][i] = max(f[2][i], cnt - v[2]);
}
FOR(s, 3, n) FOR(i, 0, m - x) if(~f[s - 1][i])
{
int pre = max(0ll, a[s - 1] - f[s - 1][i]);
FOR(j, 0, m - x - i)
{
LL L = 1ll * v[1] * j, R = 1ll * v[1] * (j + 1), cnt = R / x;
if(!j) L = -1;
if(cnt * x > L)
f[s][i + j] = max(f[s][i + j], cnt - pre - v[s]);
}
}
FOR(i, 0, m - x) if(~f[n][i]) return 1;
return 0;
}
signed main()
{
n = rd(), m = rd();
FOR(i, 1, n) v[i] = rd();
FOR(i, 1, n) a[i] = rd();
v[1] += a[1] + a[n];
int l = 0, r = m + 1;
while(l + 1 < r)
{
int mid = (l + r) >> 1;
if(chk(mid)) l = mid;
else r = mid;
}
printf("%d", l);
return 0;
}