// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
if (t<0) { putchar('-'); write(-t); return; }
if (t>9) write(t/10);
putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
typedef long long ll;
const int maxn=300*300+10;
const ll INF=1e18;
int m;
ll rub[maxn];
ll L,sum,ans;
ll *a,*b,*now=rub;
ll f[maxn*2],g[maxn*2];
int N=300*300;
ll l,r;
void solve(vector<int> &V,int flag) {
for (int i=0;i<V.size();i++) {
g[V[i]]=-INF;
for (int j=max(0LL,i+l);j<=i+r&&j<V.size();j++)
g[V[i]]=max(g[V[i]],f[V[j]]+(flag?i-j:j-i));
}
}
int main() {
//freopen("1.txt","r",stdin);
read(m); read(L);
now+=m,a=now,now+=m+1,now+=m,b=now,now+=m+1;
for (int i=-m;i<=m;i++) read(a[i]),sum+=a[i]*i;
if (sum<L) {
reverse(a-m,a+m+1),sum*=-1,L*=-1;
}
sum=0; for (int i=-m;i<0;i++) sum+=a[i]*i,b[i]=a[i];
if (sum>L) { puts("impossible"); return 0; }
for (int i=0;i<=m;i++) {
if (!i) b[i]=a[i]; else b[i]=min(a[i],(L-sum)/i);
sum+=b[i]*i;
//printf(" %lld\n",b[i]);
}
//printf("%lld %lld\n",sum,L);
for (int i=-m;i<=m;i++) ans+=b[i];
//printf("> %lld\n",ans);
for (int i=-N;i<=N;i++) f[i+N]=-INF;
f[N]=0;
for (int i=-m;i<=m;i++) if (i!=0) {
if (i<0) l=0,r=a[i]; else l=-b[i],r=a[i]-b[i];
//printf(" %d %lld %lld\n",i,abs(i)*l,abs(i)*r);
l*=-1,r*=-1,swap(l,r);
vector<int> V1;
for (int j=0;j<abs(i);j++) {
for (int k=j;k>-N;k-=abs(i)) V1.push_back(k+N);
reverse(V1.begin(),V1.end());
for (int k=j+abs(i);k<N;k+=abs(i)) V1.push_back(k+N);
solve(V1,(i>0?1:0));
}
for (int j=0;j<N*2;j++) f[j]=g[j];
}
//printf("> %lld %lld\n",L-sum,f[L-sum+N]);
if (f[L-sum+N]>=0) printf("%lld\n",f[L-sum+N]+ans);
else puts("impossible");
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Integer overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
*/
Compilation message
vault.cpp: In function 'void solve(std::vector<int>&, int)':
vault.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int i=0;i<V.size();i++) {
| ~^~~~~~~~~
vault.cpp:29:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int j=max(0LL,i+l);j<=i+r&&j<V.size();j++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4912 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4744 KB |
Output is correct |
| 4 |
Incorrect |
107 ms |
4904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4912 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4744 KB |
Output is correct |
| 4 |
Incorrect |
107 ms |
4904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
4872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
4872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
4872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4912 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4744 KB |
Output is correct |
| 4 |
Incorrect |
107 ms |
4904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
4872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4912 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4744 KB |
Output is correct |
| 4 |
Incorrect |
107 ms |
4904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
4872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4912 KB |
Output is correct |
| 2 |
Correct |
17 ms |
4872 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4744 KB |
Output is correct |
| 4 |
Incorrect |
107 ms |
4904 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
