UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#208294#3774. Circular Platform Clutterdrdilyor100653ms9068kbC++672b2024-08-02 09:39:022024-08-02 12:44:08

answer

/**
	Author: 丘成桐(囯内)
**/
#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
int n,m,k;
int a[1000005];
int mn[15];
int pre[1000005];
//区间 +, 全局 max.
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
	int res=0;
	//pre[r]-(pre[l]+k*((r-l)/m))
	for(int i=0;i<m;i++)mn[i]=(1ll<<60);
	mn[0]=0;
	for(int r=1;r<=n;r++){
		int id=(r%m-1+m)%m;
		if(mn[id]!=(1ll<<60))mn[id]+=k;
		int wp=(1ll<<60);
		for(int i=0;i<m;i++)wp=min(wp,mn[i]);
		res=max(res,a[r]-wp);
		mn[r%m]=min(mn[r%m],a[r]);
	}
	cout<<res<<"\n";
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 1ms
memory: 1272kb

input:

2000 3 16685558
-289282588 -61747468 -657707881 -34145392 -537924930 -406398379 -542751658 -75231580...

output:

0

result:

ok 1 number(s): "0"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1272kb

input:

2000 9 54576364
255242838 -740596945 -246472080 950729683 -533760302 935128112 511618036 -775471790 ...

output:

329933931328

result:

ok 1 number(s): "329933931328"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1272kb

input:

2000 9 73094302
512084424 67433847 974023247 550398283 943786443 -472874397 138837755 -744203670 539...

output:

332791924952

result:

ok 1 number(s): "332791924952"

Test #4:

score: 10
Accepted
time: 110ms
memory: 9068kb

input:

1000000 3 0
133466399 -867775767 963834867 775948067 -832740810 -713930238 -308186786 556371611 2949...

output:

647512117689

result:

ok 1 number(s): "647512117689"

Test #5:

score: 10
Accepted
time: 130ms
memory: 9068kb

input:

1000000 10 0
664925048 -566073238 877788649 -841053552 -308215965 -412748922 -840978942 -932597488 -...

output:

946593412159

result:

ok 1 number(s): "946593412159"

Test #6:

score: 10
Accepted
time: 121ms
memory: 9064kb

input:

1000000 1 383781667
797002344 -71828458 -547854034 543934687 917387704 832016545 -978766494 78233955...

output:

11338880406

result:

ok 1 number(s): "11338880406"

Test #7:

score: 10
Accepted
time: 10ms
memory: 2036kb

input:

100000 6 986672506
539233196 995762687 47061599 -854879180 810700777 -663371439 989492494 986856326 ...

output:

13786459060670

result:

ok 1 number(s): "13786459060670"

Test #8:

score: 10
Accepted
time: 15ms
memory: 2040kb

input:

100000 9 964197836
970180324 -694572429 985191372 -727965595 526258804 -617811687 -612003824 5067943...

output:

18656797316158

result:

ok 1 number(s): "18656797316158"

Test #9:

score: 10
Accepted
time: 133ms
memory: 9064kb

input:

1000000 10 944196936
-998994854 973754696 975675616 992984745 116889413 -987876256 917812370 -892363...

output:

196532701874927

result:

ok 1 number(s): "196532701874927"

Test #10:

score: 10
Accepted
time: 133ms
memory: 9064kb

input:

1000000 9 813298367
888006085 185751739 -970868688 -793265934 606885815 970133239 888746315 29012399...

output:

181821174468687

result:

ok 1 number(s): "181821174468687"