Submission #393996

#	Time	Username	Problem	Language	Result	Execution time	Memory
393996		Berted	Salesman (IOI09_salesman)	C++14	60 / 100	492 ms	44484 KiB

salesman

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
const ll INF = 1e15;
const int MX = 500001;

using namespace std;

int N, U, D, S;
vector<pii> A[MX + 1];
ll ans[MX + 1], BIT[2][MX + 1];

inline void init()
{
	for (int i = 0; i <= MX; i++) BIT[0][i] = BIT[1][i] = -INF;
}

inline void upd(int t, int i, ll val)
{
	for (; i <= MX; i += i & (-i)) {BIT[t][i] = max(BIT[t][i], val);}
}

inline ll qry(int t, int i)
{
	ll ret = -INF;
	for(; i; i -= i & (-i)) {ret = max(ret, BIT[t][i]);}
	return ret;
}

inline ll getAns(int x)
{
	return max(qry(0, MX + 1 - x) + U * x, qry(1, x) - D * x);
}

inline void ins(int x, ll v)
{
	upd(0, MX + 1 - x, v - U * x);
	upd(1, x, v + D * x);
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> U >> D >> S;
	for (int i = 0; i < N; i++)
	{
		int T, L, M; cin >> T >> L >> M;
		A[T].push_back({L, M});
	}

	init(); ins(S, 0);
	for (int i = 1; i <= MX; i++)
	{
		for (int j = 0; j < A[i].size(); j++)
		{
			ans[j] = getAns(A[i][j].fst) + A[i][j].snd;
		}
		for (int j = 0; j < A[i].size(); j++)
		{
			ins(A[i][j].fst, ans[j]);
		}
	}
	cout << getAns(S) << "\n";
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int j = 0; j < A[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~
salesman.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int j = 0; j < A[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 60 / 100