#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'
llo n,dd;
llo it[350];
llo cc[601];
llo dp[2000001];
deque<pair<llo,llo>> zz[301];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>dd;
llo cot=0;
llo ma=0;
llo acc=0;
for(llo i=0;i<n;i++){
llo aa;
cin>>aa;
cot+=aa;
cc[i]=aa;
acc+=aa;
}
llo su=0;
for(llo i=0;i<=n;i++){
cin>>it[i];
su+=it[i]*i;
cot+=it[i];
cc[n+i]=i;
}
for(llo i=0;i<=2*n;i++){
ma=max(ma,cc[i]);
}
if(ma<=100 and n<=100 and (acc==0 or n>50)){
llo xx=n*n*100;
for(llo i=0;i<=2*xx;i++){
dp[i]=-1;
}
dp[xx]=0;
for(llo j=1;j<=n;j++){
for(llo jj=0;jj<j;jj++){
zz[jj].clear();
}
llo ax=j*cc[n-j];
llo y=0;
llo z=0;
for(llo ii=0;ii<=2*xx;ii++){
// llo y=ii%j;
if(dp[ii]>=0){
pair<llo,llo> cur={dp[ii]-z,ii};
while(zz[y].size()){
if(zz[y].back().a<=cur.a){
zz[y].pop_back();
}
else{
break;
}
}
zz[y].pb(cur);
}
while(zz[y].size()){
if(zz[y].front().b<ii-ax){
zz[y].pop_front();
}
else{
break;
}
}
if(zz[y].size()){
llo xx=zz[y].front().a+z;
dp[ii]=max(dp[ii],xx);
}
y++;
if(y==j){
y=0;
z++;
}
}
}
/*for(llo i=0;i<=2*xx;i++){
if(dp[i]>=0){
cout<<i-xx<<","<<dp[i]<<endl;
}
}*/
for(llo i=0;i<=xx;i++){
swap(dp[xx+i],dp[xx-i]);
}
for(llo j=1;j<=n;j++){
for(llo jj=0;jj<j;jj++){
zz[jj].clear();
}
llo ax=j*it[j];
llo y=0;
llo z=0;
for(llo ii=0;ii<=2*xx;ii++){
// llo y=ii%j;
if(dp[ii]>=0){
pair<llo,llo> cur={dp[ii]-z,ii};
while(zz[y].size()){
if(zz[y].back().a<=cur.a){
zz[y].pop_back();
}
else{
break;
}
}
zz[y].pb(cur);
}
while(zz[y].size()){
if(zz[y].front().b<ii-ax){
zz[y].pop_front();
}
else{
break;
}
}
if(zz[y].size()){
llo xx=zz[y].front().a+z;
dp[ii]=max(dp[ii],xx);
}
y++;
if(y==j){
y=0;
z++;
}
}
}
if(dd>xx or dd<-xx){
cout<<"impossible"<<endl;
return 0;
}
if(dp[xx+dd]==-1){
cout<<"impossible"<<endl;
return 0;
}
llo ans=dp[xx+dd];
ans+=it[0];
cout<<ans<<endl;
return 0;
}
if(su<dd){
cout<<"impossible"<<endl;
return 0;
}
llo cur=su-dd;
it[0]=0;
llo ans=-1;
for(llo i=1;i<=n;i++){
llo su2=0;
llo ac=0;
for(llo j=i+1;j<=n;j++){
llo xx=it[j]-n;
if(xx<0){
xx=0;
}
ac+=xx;
su2+=xx*j;
}
if(su2>cur){
continue;
}
llo su3=0;//n*n*n;
for(llo j=1;j<i;j++){
su3+=j*min(it[j],i);
}
for(llo j=i+1;j<=n;j++){
su3+=j*min(it[j],n);
}
for(llo j=0;j<=su3;j++){
dp[j]=-1;
}
dp[0]=0;
su3=0;
for(llo j=1;j<=n;j++){
if(j==i){
continue;
}
if(j<i){
su3+=j*min(it[j],i);
}
else{
su3+=j*min(it[j],n);
}
for(llo jj=0;jj<j;jj++){
zz[jj].clear();
}
llo ax=j*min(it[j],n);
llo y=0;
llo z=0;
for(llo ii=0;ii<=su3;ii++){
// llo y=ii%j;
if(dp[ii]>=0){
pair<llo,llo> cur={dp[ii]-z,ii};
while(zz[y].size()){
if(zz[y].back().a>=cur.a){
zz[y].pop_back();
}
else{
break;
}
}
zz[y].pb(cur);
}
while(zz[y].size()){
if(zz[y].front().b<ii-ax){
zz[y].pop_front();
}
else{
break;
}
}
if(zz[y].size()){
llo xx=zz[y].front().a+z;
if(dp[ii]==-1){
dp[ii]=xx;
}
dp[ii]=min(dp[ii],xx);
}
y++;
if(y==j){
y=0;
z++;
}
}
}
llo cur2=cur-su2;
for(llo j=cur2%i;j<=su3 and j<=cur2;j+=i){
if(dp[j]>=0){
//if((cur2-j)%i==0){
llo x=(cur2-j)/i;
if(x<=it[i]){
llo y=dp[j]+x;
y+=ac;
if(ans==-1){
ans=y;
}
ans=min(ans,y);
}
//}
}
}
}
if(ans==-1){
cout<<"impossible"<<endl;
}
else{
//cout<<ans<<endl;
cout<<cot-ans<<endl;
}
//else find minimum number of elements with sum su-dd
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
383 ms |
816 KB |
Output is correct |
6 |
Incorrect |
375 ms |
844 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
383 ms |
816 KB |
Output is correct |
6 |
Incorrect |
375 ms |
844 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Incorrect |
64 ms |
1936 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Incorrect |
64 ms |
1936 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Incorrect |
64 ms |
1936 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
383 ms |
816 KB |
Output is correct |
6 |
Incorrect |
375 ms |
844 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Incorrect |
64 ms |
1936 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
383 ms |
816 KB |
Output is correct |
6 |
Incorrect |
375 ms |
844 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
596 KB |
Output is correct |
2 |
Incorrect |
64 ms |
1936 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
468 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
383 ms |
816 KB |
Output is correct |
6 |
Incorrect |
375 ms |
844 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |