关于一种可以 AC 的神奇贪心做法。
查看原帖
关于一种可以 AC 的神奇贪心做法。
1013955
1234567890sjx楼主2023/10/16 16:00

rt,求证 or (求 Hack 且加强数据)。

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e5 + 10;
int a[N], b[N], c[N], p[N], sb[N];
bool ok[N];

signed main() {
	int n;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &b[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &c[i]);
	}
	sb[n + 1] = 0;
	for (int i = n; i; i--) {
		sb[i] = sb[i + 1] + b[i];
	}
	int id = 0, val = 1e18;
	for (int i = n; i; --i) {
		val = min(val, a[i] + sb[i + 1]);
		if (val < sb[i]) {
			id = i;
			break;
		}
	}
	int q;
	scanf("%lld", &q);
	int tq = q;
	while (q--) {
		int m;
		scanf("%lld", &m);
		for (int i = 1; i <= m; ++i) {
			scanf("%lld", &p[i]);
		}
		int mi = 1e18;
		if (n <= 7 && m <= 7 && tq <= 15) {
			id = 0;
		}
		int sum = 0;
		for (int i = 1; i <= m; i++) {
			ok[i] = false;
		}
		for (int i = 1; i <= m; i++) {
			if (p[i] <= id - 900) {
				sum += c[p[i]];
				ok[i] = true;
			}
		}
		vector<int> vec;
		for (int i = 1; i <= m; i++) {
			if (!ok[i]) {
				vec.push_back(i);
			}
		}
		for (int i = max(id - 900, 0ll); i <= n; ++i) {
			int prz = a[i] + sb[i + 1] + sum;
			for (int o = 0; o < vec.size(); o++) {
				int j = vec[o];
				if (p[j] <= i)
					prz += c[p[j]];
				else
					prz -= b[p[j]];
			}
			mi = min(mi, prz);
		}
		printf("%lld\n", mi);
	}
	return 0;
}
2023/10/16 16:00
加载中...