ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#206663 | #2638. 数字选择 | marcuse | 100 | 51ms | 6808kb | C++ | 1.2kb | 2024-07-23 19:45:12 | 2024-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;
}
详细
小提示:点击横条可展开更详细的信息
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'