UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185156#2031. asnow_trace100463ms84568kbC++112.5kb2023-09-23 11:00:242023-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 
*/

Details

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

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'