Submission #32413818

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXm = 1e1;

template <typename T>
inline void read(T &a) {
	char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
	read(a), read(argv...);
}

const int MAXhx = 10237;
inline int redmod(int x) {
	return (x < 0) ? x + MAXhx : x;
}

int n, m;
int a[MAXn + 10];
int b[MAXm + 10];
int c[MAXn + 10];
int cntx, cnty, x[MAXn + 10], y[MAXn + 10];
int cntder, der[MAXn * MAXm + 10];
int px[MAXm + 10], py[MAXm + 10];

struct Ele {
	int v, cnt;
};
int cntelex, cnteley;
Ele elex[MAXn + 10], eley[MAXn + 10];

signed main() {
	read(n, m);
	for (int i = 1; i < n; ++i) {
		read(a[i]);
	}
	for (int i = 1; i <= m; ++i) {
		read(b[i]);
	}
	c[1] = b[1];
	for (int i = 2; i <= n; ++i) {
		c[i] = a[i - 1] - c[i - 1];
	}
	for (int i = 1; i <= n; i += 2) {
		x[++cntx] = c[i];
	}
	for (int i = 2; i <= n; i += 2) {
		y[++cnty] = c[i];
	}
	sort(x + 1, x + 1 + cntx);
	sort(y + 1, y + 1 + cnty);
	for (int i = 1; i <= cntx; ++i) {
		if (cntelex && elex[cntelex].v == x[i]) {
			++elex[cntelex].cnt;
		} else {
			elex[++cntelex] = Ele{x[i], 1};
		}
	}
	for (int i = 1; i <= cnty; ++i) {
		if (cnteley && eley[cnteley].v == y[i]) {
			++eley[cnteley].cnt;
		} else {
			eley[++cnteley] = Ele{y[i], 1};
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (i & 1) {
				der[++cntder] = b[j] - c[i];
			} else {
				der[++cntder] = c[i] - b[j];
			}
		}
	}
	sort(der + 1, der + 1 + cntder);
	int ans = 0;
	for (int i = 1; i <= m; ++i) {
		px[i] = cntelex;
		py[i] = 1;
	}
	for (int i = 1; i <= cntder; ++i) {
		int partans = 0;
		for (int j = 1; j <= m; ++j) {
			while (px[j] > 1 && elex[px[j]].v > b[j] - der[i]) --px[j];
			if (elex[px[j]].v == b[j] - der[i]) partans += elex[px[j]].cnt;
		}
		for (int j = 1; j <= m; ++j) {
			while (py[j] < cnteley && eley[py[j]].v < b[j] + der[i]) ++py[j];
			if (eley[py[j]].v == b[j] + der[i]) partans += eley[py[j]].cnt;
		}
		ans = max(ans, partans);
		// printf(">%lld %lld %lld\n", i, der[i], partans);
	}
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Judge Result