제출 #1338956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338956		mrbet	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	63 ms	4392 KiB

bridge

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define pb push_back
#define fi first
#define se second
#define vi vector
#define all(_v) _v.begin(), _v.end()
#define mask(_x) (1ll << (_x))
#define bit(_x,_y) (((_x) >> (_y)) & 1)
#define file "A"

string yes[2] = {"NO\n","YES\n"};
const ld eps = ld(1e-7);
const ll inf = ll(1e16) + 1;
const ll mod = ll(1e9) + 7;

template<class X, class Y>
inline bool Min(X &x, const Y &y) {
  if(x > y) {
    x = y;
    return true;
  }
  return false;
}

template<class X, class Y>
inline bool Max(X &x, const Y &y) {
  if(x < y) {
    x = y;
    return true;
  }
  return false;
}

const int N = int(1e5) +5;

int n,k,s[N],t[N];
ll suml,sumr;
vector<pii> v;
priority_queue<int> low;
priority_queue<int,vector<int>,greater<int>> up;

void ins(int x) {
    int med= (low.size() ? low.top() : 1000000001);
    if (x<=med) {
        low.push(x);
        suml+=x;
    }
    else {
        up.push(x);
        sumr+=x;
    }

    if (up.size()+1 < low.size()) {
        int nxt= low.top();
        low.pop();
        up.push(nxt);
        suml-=nxt;
        sumr+=nxt;
    }
    else if (low.size() < up.size()) {
        int nxt= up.top();
        up.pop();
        low.push(nxt);
        sumr-=nxt;
        suml+=nxt;
    }
}

ll pref[N];

void Mei () {
    cin>>k>>n;

    ll ans=0;
    forr(i,1,n) {
        char p,q;
        cin>>p>>s[i]>>q>>t[i];
        if (p==q) ans+=abs(s[i]-t[i]);
        else {
        v.pb({s[i],t[i]});
        }
    }

    v.pb({0,0});
    sort(all(v),[](pii &x, pii &y) {
         return x.fi+x.se<y.fi+y.se;
    });

    int sz= v.size()-1;
    ans+=sz;    

    suml=0, sumr=0;

    forr(i,1,sz) {
        ins(v[i].fi);
        ins(v[i].se);
        pref[i]= sumr-suml;
    }

    ll tmp= pref[sz];

    if (k==2) {
        while (low.size()) low.pop();
        while (up.size()) up.pop();
        suml=sumr=0;
        ford(i,sz,1) {
            ins(v[i].fi);
            ins(v[i].se);
            tmp=min(tmp,sumr-suml+pref[i-1]);
        }
    }

    cout<<ans+tmp;
}

void precalc() {
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(7);

  if (fopen(file".inp","r")) {
    freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
  }
  else if (fopen(file".in","r")) {
    freopen(file".in","r",stdin); freopen(file".out","w",stdout);
  }

  int tc = 1;
 // cin >> tc;
  precalc();
  while(tc--) {
    Mei();
  }

  return 0;
}
  

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:133:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:133:43: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
      |                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:136:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen(file".in","r",stdin); freopen(file".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:136:42: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |     freopen(file".in","r",stdin); freopen(file".out","w",stdout);
      |                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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