제출 #866915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866915		1075508020060209tc	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2058 ms	3600 KiB

bridge

#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int K;int n;
int obase;
pair<int,int>ar[100005];
void init(){
cin>>K>>n;
obase=0;
vector<pair<int,int>>vc;
for(int i=1;i<=n;i++){
    char a;char b;
    int pa;int pb;
    cin>>a>>pa>>b>>pb;
    if(a==b){
        obase+=abs(pa-pb);
    }else{
        obase+=abs(pa-pb)+1;
        vc.push_back({min(pa,pb),max(pa,pb)});
    }
}
n=vc.size();
for(int i=0;i<vc.size();i++){
    ar[i+1]=vc[i];
}
sort(ar+1,ar+n+1);
if(n==0){
    cout<<obase;exit(0);
}
}

void solvek1(){
int ans=1e18;
for(int i=1;i<=n;i++){
    int pl=ar[i].first;
    int cal=0;
    for(int j=1;j<=n;j++){
        if( ar[j].first<=pl&&ar[j].second>=pl ){
            continue;
        }
        cal+=2*min(abs(ar[j].first-pl),abs(ar[j].second-pl));
    }
    ans=min(ans,cal);
    pl=ar[i].second;
    cal=0;
    for(int j=1;j<=n;j++){
        if( ar[j].first<=pl&&ar[j].second>=pl ){
            continue;
        }
        cal+=2*min(abs(ar[j].first-pl),abs(ar[j].second-pl));
    }
    ans=min(ans,cal);
}
cout<<ans+obase<<endl;

}

 void solvek2(){
int ans=1e18;
vector<int>vc;
for(int i=1;i<=n;i++){
    vc.push_back(ar[i].first);
    vc.push_back(ar[i].second);
}
for(int pl2:vc){
for(int i=1;i<=n;i++){
    int pl=ar[i].first;
    int cal=0;
    for(int j=1;j<=n;j++){
        if( (ar[j].first<=pl&&ar[j].second>=pl)||(ar[j].first<=pl&&ar[j].second>=pl2) ){
            continue;
        }
        cal+=2*min(min(abs(ar[j].first-pl),abs(ar[j].second-pl)),min(abs(ar[j].first-pl2),abs(ar[j].second-pl2)));
    }
    ans=min(ans,cal);
    pl=ar[i].second;
    cal=0;
    for(int j=1;j<=n;j++){
        if( (ar[j].first<=pl&&ar[j].second>=pl)||(ar[j].first<=pl&&ar[j].second>=pl2) ){
            continue;
        }
        cal+=2*min(min(abs(ar[j].first-pl),abs(ar[j].second-pl)),min(abs(ar[j].first-pl2),abs(ar[j].second-pl2)));
    }
    ans=min(ans,cal);
}}
cout<<ans+obase<<endl;

}


signed main(){
init();
if(K==1){solvek1();}else{
    
    solvek2();
}



}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'void init()':
bridge.cpp:24:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | for(int i=0;i<vc.size();i++){
      |             ~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37