UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206663#2638. 数字选择marcuse10051ms6808kbC++1.2kb2024-07-23 19:45:122024-07-23 20:18:25

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100000 + 10;
int n,k;
int a[N],opt[N];
int sum[N],v[N];
int Pre[N],ans;
int que[N],f,r;
priority_queue < pair <int,int> > q;
int read() {
	char ch;
	int sum = 0,flag = 1;
	ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') flag = -flag;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		sum = sum * 10 + ch - '0';
		ch = getchar();
	}
	return sum * flag;
}
signed main() {
	n = read();
	k = read();
	for(int i = 1; i <= n; i++) {
		a[i] = read();
		sum[i] = sum[i - 1] + a[i];
		Pre[i] = max(1ll,i - k + 1ll);
		v[i] = sum[i] - sum[Pre[i] - 1];
	}
	f = 1,r = 0;
	for(int i = 1; i <= n; i++) {
		opt[i] = v[i];
		if(i >= k + 2) {
			q.push(make_pair(opt[Pre[i] - 2],Pre[i] - 2));
			int x = q.top().second;
			opt[i] = max(opt[i],opt[x] + v[i]);
		}
		while(que[f] < i - k && f <= r) f++;
		if(i - 2 >= 1) {
			while(opt[i - 2] - sum[i - 1] > opt[que[r]] - sum[que[r] + 1] && f <= r) r--;
			que[++r] = i - 2;
		}
		if(f <= r) opt[i] = max(opt[i],opt[que[f]] - sum[que[f] + 1] + sum[i]);
	}
	for(int i = 1; i <= n; i++) ans = max(ans,opt[i]);
	printf("%lld\n",ans);
	return 0;
}

Details

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

Test #1:

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

input:

1000 6
84050428 177260826 455862771 256918279 583384683 329013557 107945121 195924088 596694743 6928...

output:

434503208571

result:

ok single line: '434503208571'

Test #2:

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

input:

1000 3
219042030 652427252 293322782 401027209 53595955 430041101 418312352 507218364 456448805 5164...

output:

402922363192

result:

ok single line: '402922363192'

Test #3:

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

input:

1000 10
501517279 127593678 278266440 397652492 376323580 531068645 728679583 965996287 316202867 19...

output:

470645859616

result:

ok single line: '470645859616'

Test #4:

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

input:

1000 7
783992528 750243751 115726451 541761422 846534852 632096189 39046814 277290563 175956929 1610...

output:

450969583835

result:

ok single line: '450969583835'

Test #5:

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

input:

1000 4
66467777 225410177 100670109 538386705 316746124 733123733 496897692 588584839 35710991 83966...

output:

425416526140

result:

ok single line: '425416526140'

Test #6:

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

input:

1000 11
348943026 700576603 85613767 682495635 786957396 834151277 807264923 47362762 895465053 5157...

output:

474922017017

result:

ok single line: '474922017017'

Test #7:

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

input:

100000 11
181645632 343874637 415508560 628526454 172052785 178168633 680989491 95515305 155446826 4...

output:

46163228127285

result:

ok single line: '46163228127285'

Test #8:

score: 10
Accepted
time: 9ms
memory: 6776kb

input:

100000 18
464120881 819041063 252968571 772635384 642264057 279196177 991356722 554293228 15200888 7...

output:

46689586452793

result:

ok single line: '46689586452793'

Test #9:

score: 10
Accepted
time: 17ms
memory: 6768kb

input:

100000 25
746596130 294207489 237912229 769260667 112475329 380223721 301723953 865587504 874954950 ...

output:

46913205363938

result:

ok single line: '46913205363938'

Test #10:

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

input:

100000 32
29071379 916857562 75372240 913369597 582686601 481251265 759574831 176881780 734709012 22...

output:

46863053918310

result:

ok single line: '46863053918310'