Submission #572883

#	Time	Username	Problem	Language	Result	Execution time	Memory
572883		awnqwq	Uplifting Excursion (BOI22_vault)	C++14	100 / 100	545 ms	2564 KiB

vault

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define pi pair<int, int>
#define vi vector<int>
#define fi first
#define se second
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}

#define N 310
#define M (N * N * 2)
int m, val[N * 2], s[M];
ll l, a[N * 2], b[N * 2];
pi dq[M];
void uup(int *s, int w, ll cnt, int d) {
	for (int i = 0; i < w; ++i) {
		int fr = 0, ba = 0;
		for (int j = i, k = 0; j < M; j += w, ++k) {
			int cur = s[j] - k * d;
			while (fr < ba && dq[ba - 1].fi <= cur) --ba;
			dq[ba++] = mp(cur, j);
			s[j] = k * d + dq[fr].fi;
			if (dq[fr].se + cnt * w == j) ++fr;
		}
	}
}
void udown(int *s, int w, ll cnt, int d) {
	for (int i = 0; i < w; ++i) {
		int fr = 0, ba = 0, k = M / w;
		if (w * k + i >= M) --k;
		for (int j = k * w + i; k >= 0; --k, j -= w) {
			int cur = s[j] + k * d;
			while (fr < ba && dq[ba - 1].fi <= cur) --ba;
			dq[ba++] = mp(cur, j);
			s[j] = dq[fr].fi - k * d;
			if (dq[fr].se - cnt * w == j) ++fr;
		}
	}
}
void solve() {
	scanf("%d%lld", &m, &l);
	ll sum = 0;
	for (int i = 0; i < m; ++i) {
		scanf("%lld", &a[m - i - 1]);
		val[m - i - 1] = m - i;
		l += a[m - i - 1] * (m - i);
		sum += a[m - i - 1];
	}
	for (int i = 0; i <= m; ++i) {
		scanf("%lld", &a[2 * m - i]);
		val[2 * m - i] = i;
	}
	if (l < 0) {
		printf("impossible\n");
		return;
	}
	sum += a[2 * m];
	for (int i = 2 * m - 1; i >= 0; --i) {
		ll take = min(l / val[i], a[i]);
		l -= take * val[i];
		sum += take * (i >= m ? 1 : -1);
		a[i] -= take;
		b[i] += take;
		if (a[i]) break;
	}
	memset(s, 0xc3, sizeof s);
	s[M / 2] = 0;
	for (int i = 0; i < 2 * m; ++i) {
		if (a[i]) uup(s, val[i], a[i], i < m ? -1 : 1);
		if (b[i]) udown(s, val[i], b[i], i < m ? 1 : -1);
	}
	if (l < 0 || l + M / 2 >= M || s[l + M / 2] < -M) printf("impossible\n");
	else printf("%lld\n", s[l + M / 2] + sum);
}
int main() {
	int T = 1;
	//scanf("%d", &T);
	while (T--) solve();
	return 0;
}

Compilation message (stderr)

vault.cpp: In function 'void solve()':
vault.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%lld", &m, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
vault.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%lld", &a[m - i - 1]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
vault.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%lld", &a[2 * m - i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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