ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185156 | #2031. a | snow_trace | 100 | 463ms | 84568kb | C++11 | 2.5kb | 2023-09-23 11:00:24 | 2023-09-23 12:10:33 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int>p;
int l[500005],r[500005],len[500005];
int a[500005],b[500005];
int dp[100005][101][2];
bool cmp(int a,int b){
if(l[a] == l[b])return r[a]>r[b];
return l[a]<l[b];
}int ok[200005];
signed main(){
cin >> n>> k;
for(int i = 1;i<=n;i++){
cin >> l[i] >> r[i];len[i] = r[i]-l[i]+1;p.push_back(i);
}sort(p.begin(),p.end(),cmp);
vector<pair<int,int> >p1;p1.push_back({-1,-1});
int tot = 0;vector<int>pp;
for(int i =0;i<p.size();i++){
// cout << l[p[i]] << " " << r[p[i]] << endl;
if(l[p[i]]>p1.back().second){
tot++;p1.push_back({l[p[i]],r[p[i]]});ok[p[i]] = 1;
pp.clear();pp.push_back(p[i]);
}else{
if(r[p[i]]>p1.back().second){
p1.back().second = r[p[i]];
if(pp.size() == 1)tot++,pp.push_back(p[i]),ok[p[i]] = 1;
else{
// cout << r[pp[pp.size()-2]] <<" " << l[p[i]] << endl;
if(r[pp[pp.size()-2]]>=l[p[i]]){
ok[pp.back()] = 0;pp.pop_back();pp.push_back(p[i]);ok[p[i]] = 1;
}else tot++,pp.push_back(p[i]),ok[p[i]] = 1;
}
}//else if(pp.size()>1 and r[p[i]] == p1.back().second and len[p[i]]>len[pp.back()]){
// ok[pp.back()] = 0;pp.pop_back();pp.push_back(p[i]);ok[p[i]] = 1;
//}
}
}int sum = 0;
// cout << tot << endl;
vector<pair<int,int> >seg;
for(int i =0;i<p.size();i++){
if(ok[p[i]]){
seg.push_back({l[p[i]],r[p[i]]});
}
}for(int i =0;i<p1.size();i++){
sum+=p1[i].second-p1[i].first;
}for(int i =0;i<seg.size();i++){
int mx = seg[i].first,mn = seg[i].second;
// cout << mx << " " << mn << endl;
if(i!=0)mx =max(mx,seg[i-1].second);
if(i!=seg.size()-1)mn = min(mn,seg[i+1].first);
a[i+1] = mn-mx;
}
for(int i =1;i<seg.size();i++){
int dis = max((int)0,seg[i-1].second-seg[i].first);
b[i+1] = dis;
}//for(int i =1;i<=seg.size();i++)cout << a[i] << ' ';cout << endl;
//for(int i = 2;i<=seg.size();i++)cout << b[i] << " ";cout << endl;
//cout << sum << endl;
if(n-tot>=k){
cout << sum << '\n';return 0;
}memset(dp,63,sizeof(dp));
dp[0][0][0] = 0;k -= n-tot;
for(int i = 1;i<=seg.size();i++){
for(int j =0;j<=k;j++){
dp[i][j][0] = min(dp[i-1][j][1],dp[i-1][j][0]);
if(j)dp[i][j][1] = min(dp[i-1][j-1][1]+a[i]+b[i],dp[i-1][j-1][0]+a[i]);
// cout << i << " " << dp[i-1][j-1][1]+a[i]+b[i] <<" " << dp[i-1][j-1][0]+a[i] << endl;
}//cout << endl;
}int ans = min(dp[seg.size()][k][0],dp[seg.size()][k][1]);
cout << sum-ans << endl;return 0;
}/*
7 4
1 3 2 5 3 4
6 8 9 17 10 16
18 20
*/
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1280kb
input:
20 8 941374267 958239792 636546050 949277063 30572593 458894768 377940690 585510776 595907552 909524...
output:
982023824
result:
ok single line: '982023824'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1280kb
input:
20 15 76365869 433406218 633171333 786737074 131600137 929106040 44288699 688307921 419471992 769278...
output:
923804666
result:
ok single line: '923804666'
Test #3:
score: 10
Accepted
time: 1ms
memory: 1280kb
input:
20 2 358841118 908572644 771680732 777280263 232627681 399317312 146158799 355582975 95552785 629032...
output:
898648766
result:
ok single line: '898648766'
Test #4:
score: 10
Accepted
time: 4ms
memory: 1412kb
input:
5000 49 383739070 641316367 609140743 773905546 333655225 869528584 456526030 666877251 488787058 91...
output:
999604831
result:
ok single line: '999604831'
Test #5:
score: 10
Accepted
time: 5ms
memory: 1416kb
input:
5000 56 6389143 923791616 594084401 918014476 192256209 434682769 125655174 766893261 348541120 7426...
output:
999844854
result:
ok single line: '999844854'
Test #6:
score: 10
Accepted
time: 5ms
memory: 1408kb
input:
5000 63 206266865 481555569 431544412 914639759 535710313 662467481 77260492 436949450 208295182 418...
output:
999740177
result:
ok single line: '999740177'
Test #7:
score: 10
Accepted
time: 108ms
memory: 84184kb
input:
100000 95 31394575 31395303 35035434 35036166 64896609 64897277 10992021 10992677 17899328 17900254 ...
output:
74878135
result:
ok single line: '74878135'
Test #8:
score: 10
Accepted
time: 114ms
memory: 84568kb
input:
100000 83 233039267 233039367 916657359 916657459 864715109 864715209 936842396 936842496 562959930 ...
output:
9880370
result:
ok single line: '9880370'
Test #9:
score: 10
Accepted
time: 112ms
memory: 84568kb
input:
100000 90 816642137 816642237 185449925 185450025 619425312 619425412 335954840 335954940 14523568 1...
output:
9879012
result:
ok single line: '9879012'
Test #10:
score: 10
Accepted
time: 114ms
memory: 84568kb
input:
100000 85 932471751 932471851 591128329 591128429 632579047 632579147 902529780 902529880 377540930 ...
output:
9876663
result:
ok single line: '9876663'