这说明时限是1s啊,这个题1s过太困难啦
请管理员大人关注一下这个问题
这题我过了饿……等等我再提交次看看
状态: Accepted
测评机: Xeost[5]
得分: 100分
提交日期: 2010-9-8 17:37:00
有效耗时: 3875毫秒
测试结果1: 通过本测试点|有效耗时62ms
测试结果2: 通过本测试点|有效耗时94ms
测试结果3: 通过本测试点|有效耗时172ms
测试结果4: 通过本测试点|有效耗时1016ms
测试结果5: 通过本测试点|有效耗时46ms
测试结果6: 通过本测试点|有效耗时766ms
测试结果7: 通过本测试点|有效耗时156ms
测试结果8: 通过本测试点|有效耗时188ms
测试结果9: 通过本测试点|有效耗时375ms
测试结果10: 通过本测试点|有效耗时1000ms
这机子牛啊。。。。。。。。 -_-
// 鄙人又慢又长的代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
#define MAX_N 510000
#define MAX_M 1210000
#define lgN 20
typedef int nint[MAX_N];
typedef int mint[MAX_M];
typedef int lgnint[lgN];
struct node { int s, p; };
bool operator < (node a, node b) { return a.s < b.s; }
struct Heap
{
mint id, l, r, t;
node v[MAX_M];
int tot, tp;
void push(int _id, int _l, int _r, int _s, int _t)
{
tot++, id[tot] = _id, l[tot] = _l, r[tot] = _r, t[tot] = _t;
tp++, v[tp].p = tot, v[tp].s = _s;
push_heap (v + 1, v + tp + 1);
}
void top(int &_id, int &_l, int &_r, int &_s, int &_t)
{
int p = v[1].p;
_id = id[p], _l = l[p], _r = r[p], _s = v[1].s, _t = t[p];
}
void pop(void)
{
pop_heap (v + 1, v + tp + 1);
tp--;
}
};
Heap heap;
lgnint f[MAX_N], g[MAX_N];
nint sum, lgn;
lgnint po;
long long ans;
int n, m, sl, sr;
void Sparse_table(void)
{
lgn[0] = -1;
for (int i = 1, j = 0; i <= n; i++)
{
lgn[i] = lgn[i - 1];
if (po[j] == i) lgn[i]++, j++;
f[i][0] = sum[i], g[i][0] = i;
}
for (int i = 1, p = 2; i <= lgn[sr]; i++, p <<= 1)
{
for (int j = 1; j <= n - p + 1; j++)
{
int mid = j + (p >> 1);
if (f[mid][i - 1] > f[j][i - 1])
f[j][i] = f[mid][i - 1], g[j][i] = g[mid][i - 1];
else f[j][i] = f[j][i - 1], g[j][i] = g[j][i - 1];
}
}
}
int RMQ(int a, int b, int &t)
{
int lgs = lgn[b - a + 1];
if (f[a][lgs] > f[b - po[lgs] + 1][lgs]) { t = g[a][lgs]; return f[a][lgs]; }
else { t = g[b - po[lgs] + 1][lgs]; return f[b - po[lgs] + 1][lgs]; }
}
void init(void)
{
freopen ("piano.in", "r", stdin);
freopen ("piano.out", "w", stdout);
scanf ("%d%d%d%d", &n, &m, &sl, &sr);
po[0] = 1;
for (int i = 1; i < lgN; i++)
po[i] = po[i - 1] << 1;
for (int i = 1; i <= n; i++)
scanf ("%d", sum + i), sum[i] += sum[i - 1];
Sparse_table ();
}
void solve(void)
{
for (int i = 1, l, r, s, t; i <= n; i++)
{
l = i + sl - 1, r = i + sr - 1;
if (l > n) break;
if (r > n) r = n;
s = RMQ (l, r, t) - sum[i - 1];
heap.push (i, l, r, s, t);
}
for (int i = 1; i <= m; i++)
{
int id, l, r, s, t, tt;
heap.top(id, l, r, s, t), heap.pop();
ans += s;
if (l < t)
{
s = RMQ (l, t - 1, tt) - sum[id - 1];
heap.push (id, l, t - 1, s, tt);
}
if (r > t)
{
s = RMQ (t + 1, r, tt) - sum[id - 1];
heap.push (id, t + 1, r, s, tt);
}
}
}
int main(void)
{
init ();
solve ();
cout << ans;
return 0;
}