제출 #554716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554716		josanneo22	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	92 ms	5692 KiB

bridge

#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;
	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;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:14:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
bridge.cpp:114:2: note: in expansion of macro 'FOR'
  114 |  FOR(i, 0, vect.size())
      |  ^~~

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