Submission #163006

#	Time	Username	Problem	Language	Result	Execution time	Memory
163006		johutha	Salesman (IOI09_salesman)	C++14	90 / 100	1085 ms	59640 KiB

salesman

#include <map>
#include <vector>
#include <iostream>
#include <algorithm>

#define int int64_t

using namespace std;

struct fair
{
	int x, t, p;
};

struct hull
{
	map<int,int> treasuremap;
	int up;
	int down;

	int calcdist(int from, int to)
	{
		int dist = abs(to - from);
		if (from > to) return dist*up;
		return dist*down;
	}

	int query(int pos)
	{
		auto next = treasuremap.upper_bound(pos);
		int res = -1e12;
		if (next != treasuremap.end())
		{
			auto [x, v] = *next;
			res = max(res, v - calcdist(x, pos));
		}
		if (next != treasuremap.begin())
		{
			auto [x, v] = *prev(next);
			res = max(res, v - calcdist(x, pos));
		}
		return res;
	}
	
	void add(int pos, int val)
	{
		if (query(pos) > val) return;
		auto itb = treasuremap.insert({pos, val}).first;
		
		auto itn = next(itb);
		while (itn != treasuremap.end())
		{
			if (val - calcdist(pos, (*itn).first) >= (*itn).second)
			{
				itn = treasuremap.erase(itn);
			}
			else break;
		}

		while (itb != treasuremap.begin())
		{
			auto it = prev(itb);
			if (val - calcdist(pos, (*it).first) >= (*it).second)
			{
				itb = treasuremap.erase(it);
			}
			else break;
		}
	}
};

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, d, u, s;
	cin >> n >> d >> u >> s;

	map<int, vector<fair>> fairs;

	for (int i = 0; i < n; i++)
	{
		fair nf;
		cin >> nf.t >> nf.x >> nf.p;
		fairs[nf.t].push_back(nf);
	}

	/*
	cout << "\n";
	for (auto fl : fairs)
	{
		for (auto f : fl)
		{
			cout << f.t << " " << f.num << "\n";
		}
		cout << "\n";
	}*/

	hull h;
	h.up = u;
	h.down = d;
	h.add(s, 0);

	for (auto& [_, fl] : fairs)
	{
		sort(fl.begin(), fl.end(), [&](fair const& lhs, fair const& rhs) { return lhs.x < rhs.x; });
		int cn = fl.size();
		vector<int> cstr(cn);
		vector<int> cstrl(cn);
		int q = -1e12;
		int lp = -1e4;
		for (int i = 0; i < cn; i++)
		{
			cstr[i] = max(q - h.calcdist(lp, fl[i].x), h.query(fl[i].x)) + fl[i].p;
			lp = fl[i].x;
			q = cstr[i];
		}
		q = -1e12;
		lp = 1e8;
		for (int i = cn - 1; i >= 0; i--)
		{
			cstrl[i] = max(q - h.calcdist(lp, fl[i].x), h.query(fl[i].x)) + fl[i].p;
			lp = fl[i].x;
			q = cstrl[i];
		}

		for (int i = 0; i < cn; i++)
		{
			h.add(fl[i].x, max(cstr[i], cstrl[i]));
		}
	}

	cout << h.query(s) << "\n";
}

Compilation message (stderr)

salesman.cpp: In member function 'int64_t hull::query(int64_t)':
salesman.cpp:34:9: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    auto [x, v] = *next;
         ^
salesman.cpp:39:9: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    auto [x, v] = *prev(next);
         ^
salesman.cpp: In function 'int main()':
salesman.cpp:104:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto& [_, fl] : fairs)
             ^
salesman.cpp:104:19: warning: unused variable '_' [-Wunused-variable]
  for (auto& [_, fl] : fairs)
                   ^

• Subtask 1: 90 / 100