2006: [NOI2010] Super piano

Time Limit: 20 Sec  Memory Limit: 552 MB
Submit: 1296  Solved: 606
[Submit][Status]

Description

Small Z He is a famous pianist , lately C The doctor gave it to little Z A super piano , Small Z Hope to use this piano to create the most wonderful music in the world . This super piano can play n A note , The number is 1 to n. The first i The beauty of a note is Ai, among Ai Positive but negative . One “ Super chord ” It is composed of several consecutive numbered notes , It contains no less than L And not more than R. We define the beauty of a super chord as the sum of all the notes it contains . Two super chords are considered to be the same , If and only if the two super chords contain the same set of notes . Small Z Decided to create a song by k A piece of music composed of two super chords , To make the music more beautiful , Small Z The music is required to be composed of k Two different super chords . We define the beauty of a piece as the sum of all the super chords it contains . Small Z I want to know what the most wonderful music he can create .

Input

The first line contains four positive integers n, k, L, R. among n Is the number of notes ,k It is the number of super chords contained in the music ,L and R They are the lower limit and the upper limit of the number of notes contained in a super chord . Next n That's ok , Each line contains an integer Ai, Indicates the beauty of each note from small to large by number .

Output

There's only one whole number , Indicates the maximum value of the beauty of the music .

Sample Input

4 3 2 3

3

2

-6

8

Sample Output

11

【 Sample explanation 】
share 5 Two different super chords :

note 1 ~ 2, The beauty is 3 + 2 = 5
note 2 ~ 3, The beauty is 2 + (-6) = -4
note 3 ~ 4, The beauty is (-6) + 8 = 2
note 1 ~ 3, The beauty is 3 + 2 + (-6) = -1
note 2 ~ 4, The beauty is 2 + (-6) + 8 = 4
The best solution is : The music consists of chords 1, chord 3, chord 5 form , The beauty is 5 + 2 + 4 = 11.

HINT

 

Source

Answer key :
Oops , It's so moving , It was changed so quickly , I thought it was going to be a day , Don't say more , Excited
Code :( It's ugly )
 const maxn=+;inf=maxlongint;
type node=record
x,y,z:longint;
end;
var s,t:array[..,..maxn] of longint;
a,b:array[..maxn] of longint;
i,j,n,m,x,y,k,l,r,tmp:longint;
ans:int64;
c:array[..*maxn] of node;
w:node;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end; procedure modify(x,y,z:longint);
var k,i:longint;
begin
c[].x:=x;c[].y:=y;c[].z:=z;
i:=;k:=;
while k<=m do
begin
if (k<m) and (c[k+].x>c[k].x) then inc(k);
if c[].x<c[k].x then begin c[i]:=c[k];i:=k;k:=k<<;end
else k:=m+;
end;
c[i]:=c[];
end;
procedure insert(x,y,z:longint);
var k,i:longint;
begin
inc(m);c[].x:=x;c[].y:=y;c[].z:=z;
i:=m;k:=i>>;
while k>= do
begin
if c[].x>c[k].x then begin c[i]:=c[k];i:=k;k:=i>>;end
else k:=;
end;
c[i]:=c[];
end;
procedure sort(l,r:longint);
var i,j,m,temp:longint;
begin
i:=l;j:=r;x:=a[(i+j)>>];
repeat
while b[a[i]]<b[x] do inc(i);
while b[a[j]]>b[x] do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
procedure build(h,l,r:longint);
var i,p,mid:longint;
begin
mid:=(l+r)>>;p:=;
for i:=l to r do
if t[h,i]<=mid then
begin
t[h+,l+p]:=t[h,i];
inc(p);
s[h,i]:=p;
end
else
begin
t[h+,mid++i-p-l]:=t[h,i];
s[h,i]:=p;
end;
if l=r then exit;
build(h+,l,mid);
build(h+,mid+,r);
end;
function find(h,l,r,x,y,k:longint):longint;
var ll,rr,mid:longint;
begin
if l=r then exit(t[h,l]);
mid:=(l+r)>>;
if l=x then ll:= else ll:=s[h,x-];rr:=s[h,y]-ll;
if rr>=k then exit(find(h+,l,mid,l+ll,l+rr+ll-,k))
else exit(find(h+,mid+,r,mid++x-l-ll,mid++y-l-rr-ll,k-rr));
end;
procedure init;
begin
readln(n,k,l,r);inc(n);
for i:= to n do begin readln(x);b[i]:=b[i-]+x;end;
for i:= to n do a[i]:=i;
sort(,n);
end;
procedure main;
begin
for i:= to n do t[,a[i]]:=i;
build(,,n);//writeln(n);
for i:=l+ to n do
begin
tmp:=b[a[find(,,n,max(i-r,),i-l,)]];
// writeln(tmp);
insert(b[i]-tmp,i,);
end;
ans:=;
for i:= to k do
begin
w:=c[]; // writeln(w.x);
inc(ans,w.x);
if (w.z>=r-l+) or ((w.y<r+) and (w.z>w.y-l-)) then modify(-inf,inf,inf)
else
begin
tmp:=b[w.y]-b[a[find(,,n,max(w.y-r,),w.y-l,w.z+)]];
modify(tmp,w.y,w.z+);
end;
end;
writeln(ans);
end;
begin
assign(input,'input.txt');assign(output,'output.txt');
reset(input);rewrite(output);
init;
main;
close(input);close(output);
end.

NOI2010 Super piano 2 More articles about

  1. BZOJ 2006: [NOI2010] Super piano

    2006: [NOI2010] Super piano Time Limit: 20 Sec  Memory Limit: 552 MBSubmit: 2613  Solved: 1297[Submit][Statu ...

  2. Bzoj 2006: [NOI2010] Super piano Pile up ,ST surface

    2006: [NOI2010] Super piano Time Limit: 20 Sec  Memory Limit: 552 MBSubmit: 2222  Solved: 1082[Submit][Statu ...

  3. BZOJ 2006: [NOI2010] Super piano ( RMQ + Pile up )

    Take one of the biggest K individual , With piles and RMQ To speed up ... ----------------------------------------------------------------- #include<c ...

  4. BZOJ_2006_[NOI2010] Super piano _ greedy + Pile up +ST surface

    BZOJ_2006_[NOI2010] Super piano _ greedy + Pile up +ST surface Description Small Z He is a famous pianist , lately C The doctor gave it to little Z A super piano , Small Z I hope to create the most wonderful piano in the world with this piano music ...

  5. bzoj2006 [NOI2010] Super piano ( And its expansion )

    bzoj2006 [NOI2010] Super piano Given a sequence , Find the length in \([L,\ R]\) The interval between and before \(k\) The great sum \(n\leq5\times10^5,\ k\leq2\times1 ...

  6. P2048 [NOI2010] Super piano (RMQ+ Pile up + greedy )

    P2048 [NOI2010] Super piano Interval and ---> Prefix and difference Multiple query interval and maximum ---> The prefix and RMQ Take the largest interval and ---> Pile up So we set up a 3 Tuples $(o,l,r)$, To the left ...

  7. Luogu P2048 [NOI2010] Super piano Problem solving report

    P2048 [NOI2010] Super piano Title Description Small Z He is a famous pianist , lately C The doctor gave it to little Z A super piano , Small Z Hope to use this piano to create the most wonderful music in the world . This super piano can play n A note , The number is ...

  8. bzoj The thousand questions project 162:bzoj2006: [NOI2010] Super piano

    http://www.lydsy.com/JudgeOnline/problem.php?id=2006 The biggest output k individual sum[r]-sum[l-1] (L<=r-l+1<=R) The sum of the ...

  9. 【BZOJ 2006】2006: [NOI2010] Super piano (RMQ+ Priority queue )

    2006: [NOI2010] Super piano Time Limit: 20 Sec  Memory Limit: 552 MBSubmit: 2792  Solved: 1388 Description Small ...

Random recommendation

  1. javascript And Object Built-in objects

    Object.defineProperty(obj, prop, descriptor)

  2. memcache and memcahced The difference between

    Memcache What is it? ?Memcache Is a free and open source . High performance . Allocated memory object caching system . For accelerating dynamics web Applications , Reduce database load . It can handle any number of connections , Use non blocking network IO. Because of its working machine ...

  3. solve mac On Android When developing ADB server didn&#39;t ACK

    mac On adb Unable to connect to android Mobile phones can refer to : here xxxdeMacPro:~ xxx$ adb start-server * daemon not running. starting it n ...

  4. OAuth2.0 Authorization mechanism description

    Authorization mechanism description   1 brief introduction Youku is authorized to use for third party application users OAuth2.0 standard 2 OAuth2.0 Authorization way Youku supports OAuth 2.0 There are three ways to authorize , Please choose different authorization methods according to the platform : 2.1 General licensing ...

  5. Why? ERP The industry develops slowly, and the scale is difficult to expand ?

    . : The industry will only get better and better , But there are fewer and fewer enterprises that can settle down and do things , Because the benefits are really long : It's hard to really get into this industry , It's hard to get out ... I often see similar problems in Zhihu : Since all ERP The system sucks , There's no room for startups ...

  6. Kernel knowledge is the first 12 speak ,SSDT surface . In two ways from user mode to system mode .

    Kernel knowledge is the first 12 speak ,SSDT surface . In two ways from user mode to system mode . I. 1 IDT analysis . We know .IDT All kinds of interrupt information are stored in the table . For example, when we call int 3 When , It will call IDT The third item in the table .  The function ...

  7. Cocos Creator Button sound package rewriting

    cc.Button.prototype._onTouchEnded = function (t) { cc.hb.audioMgr.playMusic("click", false ...

  8. Interview questions &#183;HashMap and Hashtable The difference between ( Reprint and rearrange )

    Link to the original text : Javarevisited translate : ImportNew.com- Tang Xiaojuan Translation links : http://www.importnew.com/7010.html HashMap and Hashtabl ...

  9. Process command ps/top/kill

    process : Generally speaking, it means   A program currently executing command : ps english : process status effect : See the details of the process Options : a: Display all processes on the terminal , Include other users' processes u: Displays the detailed status of the process ...

  10. go Functions in language

    package main; import "fmt" func main() { a, b, c := A(1, 2, 3); fmt.Println(a, b, c); // call ...