526互联

AtCoder Regular Contest 092 E Both Sides Merger

发布时间 2023-07-16 20:05:18作者: zltzlt

洛谷传送门

AtCoder 传送门

Key observation：每个元素的下标奇偶性不改变。

于是讨论最后一个数是下标为奇数还是偶数加起来的数。将下标奇偶性相同的元素分开考虑。对于下标奇偶性相同的元素，不难发现答案的上界是所有 \(> 0\) 的元素之和（没有 \(> 0\) 的元素时选一个最大的），并且一定能够构造方案以达到上界。

例如，下面 O 代表对答案有贡献的元素，. 代表没有贡献的元素：

.O.O...O

方案是 .O.O...O \(\to\) O.O...O \(\to\) O...O \(\to\) O.O \(\to\) O。

因为 \(n \le 10^3\)，构造方案就直接模拟即可，复杂度 \(O(n^2)\)。

code 
// Problem: E - Both Sides Merger
// Contest: AtCoder - AtCoder Regular Contest 092
// URL: https://atcoder.jp/contests/arc092/tasks/arc092_c
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 1010;

ll n, a[maxn], t1, t2;
pii b[maxn], c[maxn], d[maxn], e[maxn];
vector<int> ans;

inline void work(int i) {
	ans.pb(i);
	if (i == 1) {
		for (int i = 1; i < n; ++i) {
			d[i] = d[i + 1];
		}
		--n;
	} else if (i == n) {
		--n;
	} else {
		int m = 0;
		for (int j = 1; j <= n; ++j) {
			if (abs(j - i) <= 1) {
				if (j == i) {
					e[++m] = make_pair(d[i - 1].fst + d[i].fst + d[i + 1].fst, d[i - 1].scd);
				}
			} else {
				e[++m] = d[j];
			}
		}
		n = m;
		for (int i = 1; i <= n; ++i) {
			d[i] = e[i];
		}
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		if (i & 1) {
			b[++t1] = make_pair(a[i], i);
		} else {
			c[++t2] = make_pair(a[i], i);
		}
	}
	sort(b + 1, b + t1 + 1, greater<pii>());
	sort(c + 1, c + t2 + 1, greater<pii>());
	ll mx = -1e18, s = 0;
	for (int i = 1; i <= t1; ++i) {
		if (i > 1 && b[i].fst < 0) {
			break;
		}
		s += b[i].fst;
		mx = max(mx, s);
	}
	s = 0;
	for (int i = 1; i <= t2; ++i) {
		if (i > 1 && c[i].fst < 0) {
			break;
		}
		s += c[i].fst;
		mx = max(mx, s);
	}
	printf("%lld\n", mx);
	s = 0;
	for (int i = 1; i <= n; ++i) {
		d[i] = make_pair(a[i], 0);
	}
	for (int i = 1; i <= t1; ++i) {
		s += b[i].fst;
		if (s == mx) {
			for (int j = 1; j <= i; ++j) {
				d[b[j].scd].scd = 1;
			}
			while (!d[1].scd) {
				work(1);
			}
			for (int j = 2; j < n; ++j) {
				if (j > 1 && d[j - 1].scd == d[j + 1].scd) {
					work(j);
					j -= 2;
				}
			}
			while (!d[n].scd) {
				work(n);
			}
			printf("%d\n", (int)ans.size());
			for (int x : ans) {
				printf("%d\n", x);
			}
			return;
		}
	}
	s = 0;
	for (int i = 1; i <= t2; ++i) {
		s += c[i].fst;
		if (s == mx) {
			for (int j = 1; j <= i; ++j) {
				d[c[j].scd].scd = 1;
			}
			while (!d[1].scd) {
				work(1);
			}
			for (int j = 2; j < n; ++j) {
				if (j > 1 && d[j - 1].scd == d[j + 1].scd) {
					work(j);
					j -= 2;
				}
			}
			while (!d[n].scd) {
				work(n);
			}
			printf("%d\n", (int)ans.size());
			for (int x : ans) {
				printf("%d\n", x);
			}
			return;
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}