Submission #163007

#TimeUsernameProblemLanguageResultExecution timeMemory
163007johuthaSalesman (IOI09_salesman)C++14
100 / 100
760 ms54052 KiB
#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 = -1e12;
		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()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...