This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF (int)(1e9 + 7)
#define INF2 998244353
#define N (ll)(3e2 + 5)
//#define f first
//#define s second
#define int ll
#define lsb(x) (x & (-x))
using namespace std;
int n, m, g, h, l;
int a[1000];
int dp1[100000], dp2[100000];
int cnt1[100000], cnt2[100000];
int sum = 0;
int f1(int x){
int sum = 0;
while(x){
sum += cnt1[x];
x -= cnt1[x] * dp1[x];
}
return sum;
}
int f2(int x){
int sum = 0;
while(x){
sum += cnt2[x];
x -= cnt2[x] * dp2[x];
}
return sum;
}
void solve(){
cin >> m >> l;
for(int i=0; i<2*m+1; i++){
cin >> a[i];
if(i > m){
sum += (i - m) * a[i];
}
}
int ans = a[m];
int cur = 0;
int t1, t2;
dp1[0] = dp2[0] = 1;
if(sum < l){
cout << "IMPOSSIBLE";
return;
}
bool bb = 0;
for(int i=m+1; i<=2*m; i++){
g = (l - cur) / (i - m);
h = min(g, a[i]);
ans += h;
cur += h * (i - m);
t1 = h;
t2 = a[i] - h;
if(cur == l)break;
for(int k=99000; k; k--){
if(dp1[k])continue;
for(int j=1; j<=t1 && j * (i - m) <= k; j++){
if(dp1[k - j * (i - m)]){
dp1[k] = (i - m);
cnt1[k] = j;
}
}
}
for(int k=99000; k; k--){
if(dp2[k])continue;
for(int j=1; j<=t2 && j * (i - m) <= k; j++){
if(dp2[k - j * (i - m)]){
dp2[k] = (i - m);
cnt2[k] = j;
}
}
}
int dif = l - cur;
for(int j=dif; j<=99000; j++){
if(dp2[j] > 0 && dp1[j - dif] > 0){
bb = 1;
ans -= f1(j - dif);
ans += f2(j);
}
}
if(bb)break;
}
if(!bb){
cout << "IMPOSSIBLE";
return;
}
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin>>T;
for(int i=1; i<=T; i++){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |