Submission #577767

#	Time	Username	Problem	Language	Result	Execution time	Memory
577767		dorijanlendvaj	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	2096 ms	12044 KiB

vault

#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;
}

void pri(vl v)
{
	for (auto x: v) cout<<x<<' ';
	cout<<en;
}

vl gen(vl c,ll l,ll r)
{
	if (r<0)
	{
		return vl(r-l+1,-LLINF);
	}
	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,min(cn,MOD*1ll),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[j],MOD*1ll),j);
			return vl(dp1.begin()+n*n,dp1.end());
		}
		++i;
	}
}

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";
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3-1: 10 / 10
• Subtask 3-2: 10 / 10
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 10 / 10
• Subtask 5-2: 10 / 10
• Subtask 6-1: 10 / 10
• Subtask 6-2: 10 / 10