UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206665#2638. 数字选择FHL10060ms2856kbC++11463b2024-07-23 19:47:212024-07-23 20:18:48

answer

#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 1e5 + 5;
LL n, k, a[N], sum[N], f[N];
int main() {
	scanf("%lld%lld", &n, &k);
	for (LL i = 1; i <= n; i ++ ) {
		scanf("%lld", &a[i]);
  		sum[i] = a[i] + sum[i - 1];
	}
	for (int i = 1; i <= n + 1; i ++ )
		for (int j = max(1LL * 0, i - k - 1); j < i; j ++ )
			f[i] = max(f[i], f[j] + sum[i - 1] - sum[j]);
	printf("%lld\n", f[n + 1]);
	return 0;
}

Details

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

Test #1:

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

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: 544kb

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: 544kb

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: 540kb

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: 540kb

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: 540kb

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: 14ms
memory: 2856kb

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: 16ms
memory: 2856kb

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: 18ms
memory: 2852kb

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: 12ms
memory: 2856kb

input:

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

output:

46863053918310

result:

ok single line: '46863053918310'