Submission #45248

#	Time	Username	Problem	Language	Result	Execution time	Memory
45248		JohnTitor	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	48 ms	22912 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Palembang_Bridges"
int k, n;
ll sure=0;
deque <pair <ll, ll> > cross;
namespace one{
    vector <ll> pos;
    void solve(){
        for(pair <ll, ll> p: cross){
            pos.pb(p.first);
            pos.pb(p.second);
        }
        sort(pos.begin(), pos.end());
        ll x=pos[pos.size()/2];
        ll res=0;
        for(ll p: pos) res+=abs(p-x);
        write(res+sure);
    }
}
//namespace one{
//    class cmp{
//    public:
//        bool operator()(pair <ll, ll> a, pair <ll, ll> b){
//            return a.second>b.second;
//        }
//    };
//    priority_queue <pair <ll, ll>, vector <pair <ll, ll> >, cmp> q;
//    set <ll> pos;
//    void solve(){
//        sort(cross.begin(), cross.end());
//        ll x=-1;
//        ll ct=0;
//        ll ax=0;
//        ll mincost=mask(60);
//        for(pair <ll, ll> p: cross){
//            ax--;
//            ct+=p.first;
//            pos.insert(p.first);
//            pos.insert(p.second);
//        }
//        mincost=min(mincost, ct+ax*x);
//        for(ll x: pos){
//            while((!q.empty())&&(q.top().second<=x)){
//                ax++;
//                ct-=q.top().second;
//                q.pop();
//            }
//            while((!cross.empty())&&(cross.front().first<=x)){
//                ax++;
//                ct-=cross.front().first;
//                q.push(cross.front());
//                cross.pop_front();
//            }
//            mincost=min(mincost, ct+ax*x);
//        }
//        writeln(sure+mincost*2);
//    }
//}
namespace two{
    void solve(){
        puts("22");
    }
}
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(k);
    read(n);
    sure=n;
    {
        char c0, c1;
        ll x0, x1;
        FOR(i, 1, n){
            while(!isalpha(c0=getchar()));
            read(x0);
            while(!isalpha(c1=getchar()));
            read(x1);
            if(c0==c1) sure+=abs(x0-x1)-1;
            else{
                if(x0>x1) swap(x0, x1);
                cross.pb(mp(x0, x1));
            }
        }
    }
    if(k==1) one::solve();
    else two::solve();
}

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