제출 #585529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585529		karrigan	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	48 ms	6532 KiB

bridge

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
struct line{
char x,z;
long long y,t;
}a[100009];
struct lena{
long long y,t;
}b[100009];
long long pf[100009];
vector<long long>c;
bool cmp(const lena &p, const lena &q){
return p.y+p.t<q.y+q.t;
}
int main()
{
    fastio
    int k,n;
    cin>>k>>n;
    int cnt=0;
    long long ans=0;
    for (int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].z>>a[i].t;
        if (a[i].x!=a[i].z){
            b[++cnt]={a[i].y,a[i].t};
            c.push_back(a[i].y);
            c.push_back(a[i].t);
            ans++;
        }
        else {
            ans+=abs(a[i].y-a[i].t);
        }
    }
    if (k==1){
        sort(c.begin(),c.end());
        int d=(int)c.size();
        d/=2;
        for (int i=0;i<(int)c.size();i++){
            if (c[i]<=c[d]){
                ans=ans+c[d]-c[i];
            }
            else ans=ans+c[i]-c[d];
        }
        cout<<ans;
        return 0;
    }
    else {
        sort(b+1,b+1+cnt,cmp);
        for (int i=1;i<cnt;i++){
            vector<long long>d;
            for (int j=1;j<=i;j++){
                d.push_back(b[j].y);
                d.push_back(b[j].t);
            }
            sort(d.begin(),d.end());
            int r=(int)d.size();
            r/=2;
            for (auto v:d){
                if (v<=d[r])pf[i]+=d[r]-v;
                else pf[i]+=v-d[r];
            }
        }
        long long cal=1e16;
        for (int i=cnt;i>1;i--){
            vector<long long>d;
            for (int j=cnt;j>=i;j--){
                d.push_back(b[j].y);
                d.push_back(b[j].t);
            }
            sort(d.begin(),d.end());
            int r=(int)d.size();
            long long gm=0;
            r/=2;
            for (auto v:d){
               if (d[r]>=v)gm+=d[r]-v;
               else gm+=v-d[r];
            }
            cal=min(cal,gm+pf[i-1]+ans);
        }
        cout<<cal;
    }
    /*
    2 5
    B 0 A 4
    B 1 B 3
    A 5 B 7
    B 2 A 6
    B 1 A 7
    */
}

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