제출 #392796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
392796		hackermub	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	440 KiB

bridge

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define float long double
#define pff pair<float,float>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(),v.end()
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)
#define forn(i,st,n,inc) for(int i=st;i<n;i+=inc)
#define rforn(i,st,n,inc) for(int i=st-1;i>=n;i-=inc)
#define bruh cout<<"\nbruh\n"; exit(0);
#define UB(v,x) upper_bound(all(v),x)
#define LB(v,x) lower_bound(all(v),x)
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pi acos(-1)
const int MOD = 1e9+7;
const int64_t INF64 = INT64_MAX;
const int32_t INF32 = INT32_MAX;


ostream& operator<<(ostream& o,const string& s){
    for(auto c:s) o<<c;
    return o;
}

template<typename F,typename S>
ostream& operator<<(ostream& o,const pair<F,S>& p){
    o<<"["<<p.fi<<","<<p.se<<"]";
    return o;
}

template<typename... T,template<class...> class C>
ostream& operator<<(ostream& o,const C<T...>& v){
    o<<"[";
    int tot=0;
    for(auto x:v){ 
        o<<x;
        if(tot<v.size()-1) o<<",";
        tot++;
    }
    o<<"]";
    return o;
}

vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef OFFLINE
clock_t Tm=clock();
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...)
#endif

void init(){
    
}

vector<pll> v;
vector<int> pre;
multiset<ll> lst,rst;
ll lsum=0,rsum=0;

void insert(int x){
    ll med=size(lst)? *--end(lst):INF32;
    if(x<=med){
        lst.insert(x);
        lsum+=x;
    }else{
        rst.insert(x);
        rsum+=x;
    }
    if(size(lst)>size(rst)+1){
        int now=*--end(lst);
        lst.erase(--end(lst));
        rst.insert(now);
        lsum-=now;
        rsum+=now;
    }else if(size(lst)<size(rst)){
        int now=*begin(rst);
        rst.erase(begin(rst));
        lst.insert(now);
        lsum+=now;
        rsum-=now;
    }
    debug(*--end(lst),lsum,rsum);
}

void solve(){
    int k,n;
    cin>>k>>n;
    ll lol=0;
    for(int i=0;i<n;i++){
        char a,b;
        ll x,y;
        cin>>a>>x>>b>>y;
        if(a==b) lol+=abs(x-y);
        else v.pb({x,y});
    }
    sort(all(v),[](pll a,pll b)->bool{
        return a.fi+a.se<b.fi+b.se;
    });
    int m=size(v);
    lol+=m;
    pre.resize(m);
    debug(v);
    for(int i=0;i<m;i++){
        insert(v[i].fi);
        insert(v[i].se);
        pre[i]=rsum-lsum;
    }
    debug(pre);
    ll ans=pre[m-1];
    if(k==2){
        lsum=0,rsum=0;
        lst.clear(),rst.clear();
        for(int i=m-1;i>0;i--){
            insert(v[i].fi);
            insert(v[i].se);
            ans=min(ans,rsum-lsum+pre[i-1]);
        }
    }
    debug(ans,lol);
    cout<<ans+lol;
} 



int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie();
    //If you hack my code , You are gay
    init();
    int T=1;
    //cin>>T;
    //scanf("%d",&T);
    while(T--){
        solve();
        //cout<<"\n";
        //printf("\n");
    }
        //mara kha
    #ifdef OFFLINE
        //cerr<<"Time = "<<(double)(clock()-Tm)/CLOCKS_PER_SEC;
    #endif
    return 0;
}

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