이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=(1LL<<60)-1;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin>>N>>M;
vector<pair<int,int>> pos(N*2);
rep(i,N){
int W,E;
cin>>W>>E;
pos[i*2]={W,i};
pos[i*2+1]={E,i};
}
sort(all(pos));
vector<pair<int,int>> tel(N,{-1,-1});
rep(i,N*2){
if(tel[pos[i].second].first==-1){
tel[pos[i].second].first=i;
}
else{
tel[pos[i].second].second=i;
}
}
vector<bool> vis(N*2,0);
int ans=0;
vector<int> more;
rep(i,N*2){
if(vis[i])continue;
int now=i;
int score=0;
while(!vis[now]){
vis[now]=1;
if(tel[pos[now].second].first==now){
now=tel[pos[now].second].second;
}
else{
now=tel[pos[now].second].first;
}
score++;
now++;
if(now==N*2)break;
}
if(i==0)ans=score;
else more.emplace_back(score);
}
sort(more.rbegin(),more.rend());
rep(i,M){
more.emplace_back(-1);
more.emplace_back(1);
ans+=more[i];
ans+=2;
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |