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>
#define x first
#define y second
#define pii pair<int,int>
using namespace std;
using ll=long long;
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int n;
ll k,c0;
ll cl[N],cr[N];
struct maxqu
{
queue<ll> q;
deque<ll> d;
void pop()
{
ll sto=q.front();
q.pop();
if (d.front()==sto) d.pop_front();
}
void push(ll x)
{
while (d.size() && d.back()<x) d.pop_back();
d.pb(x);
q.push(x);
}
ll get()
{
return d.front();
}
};
struct minqu
{
queue<ll> q;
deque<ll> d;
void pop()
{
ll sto=q.front();
q.pop();
if (d.front()==sto) d.pop_front();
}
void push(ll x)
{
while (d.size() && d.back()>x) d.pop_back();
d.pb(x);
q.push(x);
}
ll get()
{
return d.front();
}
};
vl slidmax(vl v,int s)
{
maxqu q;
vl an;
for (int i=0;i<(int)v.size();++i)
{
if (i>=s) q.pop();
q.push(v[i]);
an.pb(q.get());
}
return an;
}
vl slidmin(vl v,int s)
{
minqu q;
vl an;
for (int i=0;i<(int)v.size();++i)
{
if (i>=s) q.pop();
q.push(v[i]);
an.pb(q.get());
}
return an;
}
vl dodma(vl cdp,int cn,int w)
{
int s=cdp.size();
vl no(s);
for (int i=0;i<min(w,s);++i)
{
vl z;
for (int j=0;j*w+i<s;++j) z.pb(cdp[j*w+i]-j);
z=slidmax(z,cn+1);
for (int j=0;j*w+i<s;++j) no[j*w+i]=z[j]+j;
}
return no;
}
vl dodmi(vl cdp,int cn,int w)
{
int s=cdp.size();
vl no(s);
for (int i=0;i<min(w,s);++i)
{
vl z;
for (int j=0;j*w+i<s;++j) z.pb(cdp[j*w+i]-j);
z=slidmin(z,cn+1);
for (int j=0;j*w+i<s;++j) no[j*w+i]=z[j]+j;
}
return no;
}
vl gen(vl c,ll l,ll r)
{
int i=1;
ll s=0,cc=0;
vl dp(2*n*n+n,LLINF);
dp[0]=0;
while (1)
{
if (i<=n && c[i]*i+s<=r)
{
s+=c[i]*i;
cc+=c[i];
dp=dodmi(dp,min(c[i],MOD*1ll),i);
}
else
{
ll cn=(r-s+i-1)/i;
if (i==n+1) cn=0;
dp=dodmi(dp,cn,i);
s+=cn*i;
cc+=cn;
vl dp1;
for (ll x=l-n*n;x<=r;++x)
{
if (s>=x) dp1.pb(cc-dp[s-x]);
else dp1.pb(-LLINF);
}
if (i<=n) dp1=dodma(dp1,min(c[i]-cn,MOD*1ll),i);
for (int j=i+1;j<=n;++j) dp1=dodma(dp1,min(c[i],MOD*1ll),i);
return vl(dp1.begin()+n*n,dp1.end());
}
++i;
}
}
void pri(vl v)
{
for (auto x: v) cout<<x<<' ';
cout<<en;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>k;
ll sl=0,sr=0;
if (k<0)
{
k*=-1;
for (int i=n;i>=1;--i) cin>>cr[i];
cin>>c0;
for (int i=1;i<=n;++i) cin>>cl[i];
}
else
{
for (int i=n;i>=1;--i) cin>>cl[i];
cin>>c0;
for (int i=1;i<=n;++i) cin>>cr[i];
}
for (int i=1;i<=n;++i) sl+=cl[i]*i,sr+=cr[i]*i;
ll mal=min(sl,sr-k);
ll mil=mal-n*n;
ll mar=k+mal;
ll mir=k+mil;
vl r1=gen(vl(cl,cl+n+1),mil,mal),r2=gen(vl(cr,cr+n+1),mir,mar);
/*cout<<mil<<' '<<mal<<' '<<mir<<' '<<mar<<en;
pri(vl(cl,cl+n+1));
pri(r1);
pri(vl(cr,cr+n+1));
pri(r2);*/
ll ma=-LLINF;
for (int i=0;i<=n*n;++i) ma=max(ma,r1[i]+r2[i]);
if (ma>=0) cout<<ma+c0<<en;
else cout<<"impossible\n";
}
# | 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... |