Submission #745404

#	Time	Username	Problem	Language	Result	Execution time	Memory
745404		qwerasdfzxcl	Uplifting Excursion (BOI22_vault)	C++17	100 / 100	2919 ms	1872 KiB

vault

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int SFT = 100100, INF = 1e9 + 100;
int n, dp[2][200200];
ll L, a[1010], b[1010];

void NO(){
	printf("impossible\n");
	exit(0);
}

ll getmin(ll v, bool flag = 0){
	ll ret = 0;
	for (int i=-n;i<=n;i++){
		ret += min(v, a[i+n]) * i;
		if (flag) b[i+n] = min(v, a[i+n]);
		v -= min(v, a[i+n]);
	}

	return ret;
}

ll getmax(ll v, bool flag = 0){
	ll ret = 0;
	for (int i=n;i>=-n;i--){
		ret += min(v, a[i+n]) * i;
		if (flag) b[i+n] = min(v, a[i+n]);
		v -= min(v, a[i+n]);
	}

	return ret;
}

ll getX(ll S, ll mS, ll pS){
	if (L < getmin(mS)) NO();
	if (L > getmax(pS)) NO();

	ll l = mS, r = S;
	ll vmn = mS;
	while(l<=r){
		ll mid = (l+r)>>1;
		if (getmin(mid) <= L) vmn = mid, l = mid+1;
		else r = mid-1;
	}

	l = pS, r = S;
	ll vmx = pS;
	while(l<=r){
		ll mid = (l+r)>>1;
		if (getmax(mid) >= L) vmx = mid, l = mid+1;
		else r = mid-1;
	}

	ll v = min(vmn, vmx);
	if (L < getmin(v) || getmax(v) < L) NO();
	return v;
}

void f(int z, int b, int c, int x, int d){
	// printf(" %d %d %d %d\n", b, c, x, d);
	if (x==0){
		for (int i=-b;i<=b;i++){
			dp[z][i+SFT] = dp[z^1][i+SFT];
			if (d<0) dp[z][i+SFT] -= c;
		}
	}

	else if (x>0){
		assert(-b+x < 0);
		for (int p=-b;p<-b+x;p++){
			list<pair<int, int>> dq;
			for (int i=p,j=0 ; i<=b ; i+=x,j++){
				while(!dq.empty() && dq.back().first+j*d >= dp[z^1][i+SFT]) dq.pop_back();
				while(!dq.empty() && j-dq.front().second > c) dq.pop_front();
				dq.emplace_back(dp[z^1][i+SFT]-j*d, j);

				dp[z][i+SFT] = dq.front().first + j*d;
			}
		}
	}

	else{
		x = -x;
		assert(b-x > 0);
		for (int p=b;p>b-x;p--){
			list<pair<int, int>> dq;
			for (int i=p,j=0 ; i>=-b ; i-=x,j++){
				while(!dq.empty() && dq.back().first+j*d >= dp[z^1][i+SFT]) dq.pop_back();
				while(!dq.empty() && j-dq.front().second > c) dq.pop_front();
				dq.emplace_back(dp[z^1][i+SFT]-j*d, j);

				dp[z][i+SFT] = dq.front().first + j*d;
			}
		}
	}

	// for (int i=-5;i<0;i++) printf("%d ", dp[z][i+SFT]);
	// printf("| ");
	// for (int i=0;i<=5;i++) printf("%d ", dp[z][i+SFT]);
	// printf("\n");
}

void solve(ll X){
	// printf("X = %lld\n", X);
	ll mn = getmin(X), mx = getmax(X);
	assert(abs(mn-L) < n || abs(mx-L) < n);
	if (abs(mn-L) >= n){
		L = -L;
		reverse(a, a+n*2+1);
		mn = getmin(X), mx = getmax(X);
	}
	getmin(X, 1);

	ll r = n*2 + 2, B = n*n + 1000;
	int z = 0;

	fill(dp[0]-B+SFT, dp[0]+B+SFT+1, INF);
	dp[0][SFT] = 0;

	for (int i=-n;i<=n;i++){
		if (b[i+n] > 0){
			z ^= 1;
			fill(dp[z]-B+SFT, dp[z]+B+SFT+1, INF);
			f(z, B, min(b[i+n], r), -i, 1);
		}
		if (b[i+n] < a[i+n]){
			z ^= 1;
			fill(dp[z]-B+SFT, dp[z]+B+SFT+1, INF);
			f(z, B, min(a[i+n]-b[i+n], r), i, -1);
		}
	}

	ll need = L-mn;
	if (dp[z][need+SFT]>INF-200200) NO();
	printf("%lld\n", X-dp[z][need+SFT]);
}

int main(){
	scanf("%d %lld", &n, &L);
	ll S = 0, mS = 0, pS = 0;
	for (int i=-n;i<=n;i++){
		scanf("%lld", a+i+n);
		S += a[i+n];
		if (i<0) mS += a[i+n];
		else if (i>0) pS += a[i+n];
	} 

	solve(getX(S, mS, pS));
}

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d %lld", &n, &L);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
vault.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |   scanf("%lld", a+i+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