제출 #45248

#제출 시각아이디문제언어결과실행 시간메모리
45248JohnTitorPalembang Bridges (APIO15_bridge)C++11
22 / 100
48 ms22912 KiB
#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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...