Submission #162976

#	Time	Username	Problem	Language	Result	Execution time	Memory
162976		johutha	Salesman (IOI09_salesman)	C++14	40 / 100	1075 ms	54080 KiB

salesman

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

#define int int64_t

using namespace std;

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

bool faircomp(fair f1, fair f2)
{
	if (f1.t != f2.t) return f1.t < f2.t;
	return f1.x < f2.x;
}

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 = -1e9;
		if (next != treasuremap.end())
		{
			int x = (*next).first;
			int v = (*next).second;
			res = max(res, v - calcdist(x, pos));
		}
		if (next != treasuremap.begin())
		{
			auto bef = prev(next);
			int x = (*bef).first;
			int v = (*bef).second;
			res = max(res, v - calcdist(x, pos));
		}
		return res;
	}
	
	void add(int pos, int val)
	{
		if (query(pos) > val) return;
		treasuremap.insert({pos, val});
		map<int,int>::iterator itn = next(treasuremap.find(pos));
		map<int,int>::iterator itb = treasuremap.find(pos);

		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()
{
	int n, d, u, s;
	cin >> n >> d >> u >> s;

	map<int,int> active;
	vector<fair> ofairs;

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

	sort(ofairs.begin(), ofairs.end(), faircomp);

	vector<vector<fair>> fairs;
	int last = -1;
	vector<fair> cf;
	for (auto f : ofairs)
	{
		if (f.t != last)
		{
			if (last != -1)
			{
				fairs.push_back(cf);
				cf.clear();
			}
		}
		last = f.t;
		cf.push_back(f);
	}
	fairs.push_back(cf);

	/*
	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)
	{
		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";
}

• Subtask 1: 40 / 100