#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
ll A[5000];
vector<ll>knapsack(int n,vector<int>item){
vector<ll>dp(n+1,-1e18);
dp[0] = 0;
int m = item.size()-1;
for(int i=1;i<=m;i++){
int x = item[i];
int z = 1;
while(x>=z){
x-=z;
for(int j=n;j>=i*z;j--)dp[j] = max(dp[j],dp[j-i*z] + z);
z*=2;
}
if(x)for(int j=n;j>=i*x;j--)dp[j] = max(dp[j],dp[j-i*x] + x);
}
return dp;
}
int main()
{
ll m,L;
cin>>m>>L;
for(int i=-m;i<=m;i++)cin>>A[i+m];
//greedy sol and optimal sol distance small
ll neg = 0,pos = 0;
for(ll i=-m;i<=0;i++)neg+=i*A[i+m];
for(ll i=0 ;i<=m;i++)pos+=i*A[i+m];
if(!(neg<=L && L<=pos)){
cout<<"impossible";
return 0;
}
if(neg+pos<L){
cout<<"impossible"<<'\n';
return 0;
}//cout<<neg<<" "<<pos<<" "<<L<<'\n';
ll cur = 0;
vector<int>item(m+1);
for(int i=-m;i<0;i++)item[-i] = min(2*m,A[i+m]);
vector<ll>dp1 = knapsack(2*m,item);
for(ll i=1;i<=m;i++){
if(neg+i > L)break;
ll take = min((L-neg)/i ,A[i+m]);
A[i+m]-=take;
neg+=take*i;
cur+=take;
item[i] = min(2*m,A[i+m]);
}
//cout<<neg<<" "<<cur<<'\n';
vector<ll>dp2 = knapsack(2*m,item);
int need = L-neg;
ll ans = -1e18;
for(int i=need;i<=2*m;i++){
if(dp2[i] >=0 && dp1[i-need]>=0)ans = max(ans,dp2[i] + dp1[i-need]);
}
if(ans==-1e18)cout<<"impossible"<<'\n';
else cout<<ans + A[m] + cur<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
