Submission #866913

#	Time	Username	Problem	Language	Result	Execution time	Memory
866913		1075508020060209tc	Palembang Bridges (APIO15_bridge)	C++14	8 / 100	2095 ms	4352 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;

}




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



}

Compilation message (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