观察可以发现:
- 使每支箭的距离都为 \(D\) 一定不劣;
- 每支箭坐标一定为整数;
- 设最左边的箭坐标为 \(x\),那么 \(x\) 太小时可以把最左边的箭移到最右边,\(x\) 太大时可以把最右边的箭移到最左边。计算可得 \(x\) 的最优取值范围为 \(x \in [-\left\lfloor\frac{ND}{2}\right\rfloor, -\left\lfloor\frac{ND}{2}\right\rfloor + D)\)。
这样枚举 \(x\) 就得到了一个 \(O(mD)\) 做法。
考虑与其单独算每个 \(x\) 的得分,不如把所有 \(x\) 放在一起考虑,单独算每个线段的贡献。预处理出 \((l_i, r_i, v_i)\) 表示坐标落在 \([l_i, r_i)\) 的箭能得 \(v_i\) 分,对于一个固定的 \(x\),差分可得坐标落在这个区间内的箭的数量为:
\[\max(\min(\left\lceil\frac{r_i - x}{D}\right\rceil, n), 0) - \max(\min(\left\lceil\frac{l_i - x}{D}\right\rceil, n), 0)
\]
发现因为 \(x\) 取值区间长度为 \(D\),所以上面式子中左、右项的值最多变一次。二分出极长相同区间后,对这个范围的 \(x\) 的答案区间加上面式子乘上 \(v_i\),可以使用差分。
时间复杂度 \(O(m \log D + D)\)。
code
// Problem: D - AtArcher
// Contest: AtCoder - AtCoder Regular Contest 131
// URL: https://atcoder.jp/contests/arc131/tasks/arc131_d
// Memory Limit: 1024 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 long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
ll n, m, K, A, a[maxn], b[maxn], D, d[maxn];
struct node {
ll l, r, x;
node(ll a = 0, ll b = 0, ll c = 0) : l(a), r(b), x(c) {}
} c[maxn];
// [l, r)
inline ll calc(ll t, ll x) {
return x < t ? min((t - x + D - 1) / D, n) : 0;
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &D);
A = -(n * D / 2);
for (int i = 0; i <= m; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i]);
}
for (int i = m; i >= 2; --i) {
c[++K] = node(-a[i], -a[i - 1], b[i]);
}
c[++K] = node(-a[1], a[1] + 1, b[1]);
for (int i = 2; i <= m; ++i) {
c[++K] = node(a[i - 1] + 1, a[i] + 1, b[i]);
}
for (int i = 1; i <= K; ++i) {
ll L = c[i].l, R = c[i].r, x = c[i].x, p = A;
while (p <= A + D - 1) {
ll l = p, r = A + D - 1, pos = -1, u = calc(L, p), v = calc(R, p);
while (l <= r) {
ll mid = (l + r) >> 1;
if (calc(L, mid) == u && calc(R, mid) == v) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[p - A + 1] += (v - u) * x;
d[pos + 1 - A + 1] -= (v - u) * x;
p = pos + 1;
}
}
ll ans = 0;
for (int i = 1; i <= D; ++i) {
d[i] += d[i - 1];
ans = max(ans, d[i]);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtArcher AtCoder Regular Contest 131atarcher atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder subsegments atcoder regular contest