不妨假设$L\le \sum_{|i|\le n}i\cdot a_{i}$，否则可以交换$a_{i}$和$a_{-i}$并将$L$取相反数

贪心：$\forall i\le 0$取$a_{i}$个$i$，$\forall i>0$依次取$\lfloor\frac{L-L_{now}}{i}\rfloor$个$i$（其中$L_{now}$为当前元素和）

注意到最终$L_{now}\in (L-m,L]$（若$L<L_{now}$显然无解），并考虑调整：

任取最优解，每次加入/删除一个元素，根据贪心$加入的最小元素>0,删除的最大元素$

每次调整至多使得$L_{now}\pm m$，最终$L_{now}=L$，则存在一种方式使得$|L-L_{now}|\le m$

若某个$L_{now}$重复出现，记其间加入和删除的数分别为$A$和$B$，则$\sum_{x\in A}x=\sum_{x\in B}x$

结合前者的性质，不难证明$|A|<|B|$，进而这一段调整使得元素个数减少，无意义

换言之，每一个$L_{now}$至多出现$1$次，共计至多调整$o(m)$次，进而背包值域为$o(m^{2})$

使用单调队列优化，总复杂度为$o(m^{3})$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1000
 4 #define M 400000
 5 #define ll long long
 6 int n,S,q[M];ll m,sum,ans,a[N],b[N],g[M],f[M];
 7 void turn(int i,int p,ll cnt){
 8     if (i>0){
 9         for(int j=0;j<i;j++){
10             int l=1,r=0;
11             for(int k=j;k<=(S<<1);k+=i){
12                 if (f[k]>=0){
13                     g[k]=f[k]-p*(k/i);
14                     while ((l<=r)&&(g[q[r]]<g[k]))r--;
15                     q[++r]=k;
16                 }
17                 while ((l<=r)&&(q[l]<k-cnt*i))l++;
18                 f[k]=(l<=r ? g[q[l]]+p*(k/i) : -1);
19             }
20         }
21     }
22     else{
23         for(int j=0;j<-i;j++){
24             int l=1,r=0;
25             for(int k=(S<<1)-j;k>=0;k+=i){
26                 if (f[k]>=0){
27                     g[k]=f[k]-p*(k/i);
28                     while ((l<=r)&&(g[q[r]]<g[k]))r--;
29                     q[++r]=k;
30                 }
31                 while ((l<=r)&&(q[l]>k-cnt*i))l++;
32                 f[k]=(l<=r ? g[q[l]]+p*(k/i) : -1);
33             }
34         }
35     }
36 }
37 int main(){
38     scanf("%d%lld",&n,&m);
39     for(int i=-n;i<=n;i++){
40         scanf("%lld",&a[i+n]);
41         sum+=i*a[i+n];
42     }
43     if (m>sum)m=-m,reverse(a,a+(n<<1)+1);
44     S=2*n*n,sum=0;
45     for(int i=-n;i<=0;i++){
46         b[i+n]=a[i+n];
47         sum+=i*b[i+n],ans+=b[i+n];
48     }
49     if (m<sum){
50         printf("impossible\n");
51         return 0;
52     }
53     for(int i=1;i<=n;i++){
54         b[i+n]=min((m-sum)/i,a[i+n]);
55         sum+=i*b[i+n],ans+=b[i+n];
56     }
57     memset(f,-1,sizeof(f));
58     f[S]=ans;
59     for(int i=-n;i<=n;i++)turn(-i,-1,b[i+n]),turn(i,1,a[i+n]-b[i+n]);
60     if (f[S+(m-sum)]<0)printf("impossible\n");
61     else printf("%lld\n",f[S+(m-sum)]);
62     return 0;
63 }