제출 #494091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494091		pooyashams	Palembang Bridges (APIO15_bridge)	C++14	41 / 100	109 ms	32004 KiB

bridge

#include <algorithm>
#include <numeric>
#include <iostream>
#include <cstring>
#include <numeric>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2012;

bool isimp[maxn];
int hpos[maxn];
int wpos[maxn];
int imps[maxn];
map<int, int> pidx;
vector<int> poses = {0};
int stat[maxn];
int enat[maxn];
int ncnt[maxn];
int bcnt[maxn];
int menat[maxn];
ll nsum[maxn];
ll bsum[maxn];
ll dp[maxn][maxn];

int icnt = 0;

struct cmp
{
	int l;
	cmp(int _l)
	{
		l = _l;
	}
	inline int diff(int i)
	{
		//return hpos[i] - poses[l] + wpos[i] - poses.back();
		return poses.back() + poses[l] - hpos[i] - wpos[i];
	}
	inline bool operator()(int i, int j)
	{
		return diff(i) > diff(j);
	}
};

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k; cin >> k >> n; // k = 1
	for(int i = 0; i < n; i++)
	{
		char a, b;
		int c, d;
		cin >> a >> c >> b >> d;
		hpos[i] = min(c, d);
		wpos[i] = max(c, d);
		poses.push_back(c);
		poses.push_back(d);
		isimp[i] = (a != b);
	}
	sort(poses.begin(), poses.end());
	poses.resize(unique(poses.begin(), poses.end()) - poses.begin());
	poses.push_back(poses.back()+1);
	const int m = poses.size();
	for(int i = 0; i < m; i++)
	{
		pidx[poses[i]] = i;
	}
	for(int i = 0; i < n; i++)
	{
		if(isimp[i])
		{
			imps[icnt++] = i;
			stat[pidx[hpos[i]]]++;
			enat[pidx[wpos[i]]]++;
			nsum[0] += hpos[i];
		}
	}
	ncnt[0] = icnt;
	for(int i = 1; i < m; i++)
	{
		ll x = poses[i] - poses[i-1];
		ncnt[i] = ncnt[i-1] - stat[i-1];
		bcnt[i] = bcnt[i-1] + enat[i-1];
		nsum[i] = nsum[i-1] - x*ncnt[i];
		bsum[i] = bsum[i-1] + x*bcnt[i];
	}
	for(int l = 0; l < m; l++)
	{
		vector<int> midimps;
		memset(menat, 0, sizeof menat);
		int bc = 0;
		for(int idx = 0; idx < icnt; idx++)
		{
			int i = imps[idx];
			if(hpos[i] > poses[l])
			{
				dp[l][m-1] += min(hpos[i] - poses[l], poses.back() - wpos[i]);
				if(hpos[i] - poses[l] < poses.back() - wpos[i])
				{
					midimps.push_back(i);
				}
				else
				{
					menat[pidx[wpos[i]]]++;
					bc++;
				}
			}
		}
		sort(midimps.begin(), midimps.end(), cmp(l));
		//ll w = 0;
		for(int r = m-2; r >= 0; r--)
		{
			dp[l][r] = dp[l][r+1];
			ll w = poses[r+1] - poses[r];
			dp[l][r] -= w * bc;
			while(!midimps.empty() and hpos[midimps.back()] - poses[l] > poses[r] - wpos[midimps.back()])
			{
				dp[l][r] -= hpos[midimps.back()] - poses[l];
				dp[l][r] += poses[r] - wpos[midimps.back()];
				if(wpos[midimps.back()] < poses[r])
				{
					bc++;
					menat[pidx[wpos[midimps.back()]]]++;
				}
				midimps.pop_back();
			}
			bc -= menat[r];
		}
	}
	ll mndp = 1e17;
	int anl = 0;
	int anr = 0;
	for(int l = 0; l < m; l++)
	{
		for(int r = 0; r < m; r++)
		{
			if(bsum[l] + dp[l][r] + nsum[r] < mndp)
			{
				mndp = bsum[l] + dp[l][r] + nsum[r];
				anl = l;
				anr = r;
			}
		}
	}
	cerr << anl << " " << anr << " " << mndp << endl;
	ll out = 0;
	for(int i = 0; i < n; i++)
	{
		if(isimp[i])
		{
			out += min( abs(wpos[i] - poses[anl]) + abs(hpos[i] - poses[anl]), abs(wpos[i] - poses[anr]) + abs(hpos[i] - poses[anr]) );
			out++;
		}
		else
		{
			out += wpos[i] - hpos[i];
		}
	}
	cout << out << endl;
	return 0;
}

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