Submission #544522

#	Time	Username	Problem	Language	Result	Execution time	Memory
544522		blue	Sightseeing in Kyoto (JOI22_kyoto)	C++17	100 / 100	675 ms	26956 KiB

kyoto

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using ll = long long;

struct road
{
	ll n;
	
	ll i1;
	ll i2;

	int t; //0 = horizontal = A, 1 = vertical = B
};

bool operator < (road A, road B)
{
	if(A.n*(B.i2 - B.i1) != B.n*(A.i2 - A.i1)) 
		return A.n*(B.i2 - B.i1) < B.n*(A.i2 - A.i1);
	else if(A.t != B.t) 
		return A.t < B.t;
	else 
		return A.i1 < B.i1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int H, W;
	cin >> H >> W;

	ll A[1+H], B[1+W];
	for(ll i = 1; i <= H; i++) cin >> A[i];
	for(ll j = 1; j <= W; j++) cin >> B[j];

	set<road> R;
	for(ll i = 1; i < H; i++)
		R.insert({A[i] - A[i+1], i, i+1, 0});

	for(ll j = 1; j < W; j++)
		R.insert({B[j] - B[j+1], j, j+1, 1});

	set<ll> I, J; //alive indices, where there is a valid road.
	for(ll i = 1; i <= H; i++) I.insert(i);
	for(ll j = 1; j <= W; j++) J.insert(j);

	ll ci = 1, cj = 1;

	ll cost = 0;

	// for(road r : R) cerr << r.t << ' ' << r.n << '/' << r.i2-r.i1 << '\n';

	// cerr << "road = \n";
	// 	for(auto r : R) cerr << r.n << ' ' << r.i1 << ' ' << r.i2 << ' ' << r.t << '\n';

	while(!(ci == H && cj == W))
	{
		// cerr << "\n\n\n";
		if(*I.begin() > ci)
		{
			cost += B[*J.begin()] * (*I.begin() - ci);
			ci = *I.begin();
			// cerr << "go down\n";
			continue;
		}

		if(*J.begin() > cj)
		{
			cost += A[*I.begin()] * (*J.begin() - cj);
			cj = *J.begin();
			// cerr << "go right\n";
			continue;
		}

		road r = *R.rbegin();
		R.erase(r);
		// cerr << "erase\n";

		if(r.t == 0)
		{
			ll ri = r.i1;
			ll rnxt = r.i2;

			// cerr << "remove horizontal road " << ri << '\n';
 
			I.erase(ri);

			auto it = I.lower_bound(ri);
			if(it == I.begin()) continue;
			it--;

			ll rprv = *it;

			R.erase({A[rprv] - A[ri], rprv, ri, 0});

			R.insert({A[rprv] - A[rnxt], rprv, rnxt, 0});
			// cerr << "insert\n";
		}
		else
		{
			ll ri = r.i1;
			ll rnxt = r.i2;

			// cerr << "remove vertical road " << ri << '\n';

			J.erase(ri);

			auto it = J.lower_bound(ri);
			if(it == J.begin()) continue;
			it--;

			ll rprv = *it;

			R.erase({B[rprv] - B[ri], rprv, ri, 1});

			R.insert({B[rprv] - B[rnxt], rprv, rnxt, 1});
			// cerr << "insert\n";
		}

		// cerr << "road = \n";
		// for(auto r : R) cerr << r.n << ' ' << r.i1 << ' ' << r.i2 << ' ' << r.t << '\n';
	}

	cout << cost << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60