| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 554715 | josanneo22 | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (a); i > (b); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define mp make_pair
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second
#define out(x) cout<<x;
#define in(x) cin>>x;
#define inarr(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define incor(a,x,y) for(int i=x;i<y;i++){cin>>a[i].f>>a[i].s;}
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
const int mod = 1e9 + 7;
bool cmp(pii p1, pii p2)//ascending
{
return p1.f + p1.s < p2.f + p2.s;
}
void normal()
{
ios_base::sync_with_stdio(0); cin.tie(0);
}
ll ex(int base, int power)
{
if (power == 0)
return 1;
ll result = ex(base, power / 2);
if (power % 2 == 1)
return(((result * result) % mod) * base) % mod;
else return (result * result) % mod;
}
int k, n;
priority_queue<int> lft;//descending
priority_queue<int, vi, greater<int> > rgt;// ascending
ll lsum, rsum;
void add(int x)
{
int median;
if (lft.empty())
median = 1e9 + 1;
else
median = lft.top();
if (x <= median)
{
lft.push(x);
lsum += x;
}
else
{
rgt.push(x);
rsum += x;
}
if (rgt.size() + 1 < lft.size())
{
int nxt = lft.top();
lft.pop();
rgt.push(nxt);
lsum -= nxt;
rsum += nxt;
}
else if (lft.size() < rgt.size())
{
int nxt = rgt.top();
rgt.pop();
lft.push(nxt);
rsum -= nxt;
lsum += nxt;
}
}
ll pref[100001];
int main()
{
normal();
ll cnt = 0;
vpii vect;
cin >> k >> n;
pref.rsz(n + 1);
FOR(i, 0, n)
{
char a, b;
int x, y;
cin >> a >> x >> b >> y;
if (a == b)
cnt += abs(x - y);// as same zone does require the citizen to cross a bridge, we just need to add distance between x and y
else
vect.pb({ x, y });
}
sort(all(vect), cmp);
cnt += vect.size();// adds because requires 1 step to go throught the bridge
FOR(i, 0, vect.size())
{
add(vect[i].f);
add(vect[i].s);
pref[i] = rsum - lsum;// distance from this vect[i to 0] to bridge 1
}
ll ans = pref[vect.size()-1];
if (k == 2)
{
while (lft.size()) lft.pop();// reset to calculate distance from the current vect[i to n] to bridge 2
while (rgt.size()) rgt.pop();
lsum = rsum = 0;
ROF(i,vect.size()-1, 0)
{
add(vect[i].f);
add(vect[i].s);
ans = min(ans, (ll)rsum - lsum + pref[i - 1]);//if all the citizens from (i to n) all picked bridge 2 then just add pref[i-1]
// because pref[i-1] keeps the distance from vect[i-1 to 0] to bridge 1 and we assume taht all before i goes to bridge 1
}
}
cout << cnt + ans;
return 0;
}