1 条题解
-
1
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #define MAXN 500005 #define LOG 20 #define max(x, y) ((x) > (y) ? (x) : (y)) #define min(x, y) ((x) < (y) ? (x) : (y)) long long sum[MAXN], table[MAXN][LOG]; namespace RMQ { void init(int n) { for (int i = 1; i <= n; i++) table[i][0] = i; for (int j = 1; (1 << j) <= n; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) { int x = table[i][j - 1], y = table[i + (1 << (j - 1))][j - 1]; table[i][j] = sum[x] > sum[y] ? x : y; } } int query(int l, int r) { int k = log2(r - l + 1); int x = table[l][k], y = table[r - (1 << k) + 1][k]; return sum[x] > sum[y] ? x : y; } } struct element { int o, l, r, t; element() {} element(int o, int l, int r) : o(o), l(l), r(r), t(RMQ::query(l, r)) {} friend bool operator < (const element& a, const element& b) { return sum[a.t] - sum[a.o - 1] < sum[b.t] - sum[b.o - 1]; } }; std::priority_queue< element > Q; int main() { int n, k, L, R; scanf("%d%d%d%d", &n, &k, &L, &R); for (int i = 1; i <= n; i++) { scanf("%lld", &sum[i]); sum[i] += sum[i - 1]; } RMQ::init(n); for (int i = 1; i <= n; i++) if (i + L - 1 <= n) Q.push(element(i, i + L - 1, min(i + R - 1, n))); long long ans = 0; while (k--) { int o = Q.top().o, l = Q.top().l, r = Q.top().r, t = Q.top().t; Q.pop(); ans += sum[t] - sum[o - 1]; if (l != t) Q.push(element(o, l, t - 1)); if (t != r) Q.push(element(o, t + 1, r)); } printf("%lld\n", ans); return 0; }
- 1
信息
- ID
- 1008
- 时间
- 2000ms
- 内存
- 500MiB
- 难度
- 6
- 标签
- 递交数
- 17
- 已通过
- 5
- 上传者