Submission #53582

#	Time	Username	Problem	Language	Result	Execution time	Memory
53582		ho94949	Salesman (IOI09_salesman)	C++17	100 / 100	962 ms	36836 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 524288;
const int INF = 0x3f3f3f3f;
//day, place, price
vector<pair<int, int> > market[MAXN];
 
struct Tree
{
	int idx[2*MAXN];
	void init()
	{
		memset(idx, 0xc0, sizeof idx);
	}
	void setv(int a, int v)
	{
		a += MAXN;
		idx[a]=max(idx[a], v);
		while((a=a/2))
			idx[a] = max(idx[2*a], idx[2*a+1]);
	}
	int getv(int a, int b)
	{
		a += MAXN; b += MAXN;
		int res = -INF;
		while(a<=b)
		{
			if(a%2==1) res = max(res, idx[a++]);
			if(b%2==0) res = max(res, idx[b--]);
			a /= 2; b /= 2;
		}
		return res;
	}
}UTree, DTree; 
int N, U, D, S;
 
void setv(int a, int v)
{
	DTree.setv(a, v+D*a);
	UTree.setv(a, v-U*a);
}
int getv(int a)
{
	int ans = max(DTree.getv(0, a) - D*a, UTree.getv(a, MAXN-1) + U*a);
	return ans;
}
 
void solve(vector<pair<int, int> >& market)
{
	if(market.size() == 0) return;
	sort(market.begin(), market.end());
	vector<int> Uv(market.size());
	vector<int> Dv(market.size());
	for(int i=0; i<market.size(); ++i)
		Uv[i] = Dv[i] = getv(market[i].first);
	for(int i=0; i<market.size(); ++i)
	{
		if(i != 0)
			Dv[i] = max(Dv[i], Dv[i-1] - D*(market[i].first-market[i-1].first));
		Dv[i] += market[i].second;
	}
	for(int i=market.size()-1; i>=0; --i)
	{
		if(i != market.size()-1)
			Uv[i] = max(Uv[i], Uv[i+1] - U*(market[i+1].first-market[i].first));
		Uv[i] += market[i].second;
	}
	for(int i=0; i<market.size(); ++i)
		setv(market[i].first, max(Dv[i], Uv[i]));
}
 
int main()
{
	int St;
	scanf("%d%d%d%d", &N, &U, &D, &S);
	for(int i=0; i<N; ++i)
	{
		int t, l, m; scanf("%d%d%d", &t, &l, &m);
		market[t].emplace_back(l, m);
	}
	UTree.init(); DTree.init();
	setv(S, 0);
	for(int i=1; i<=500001; ++i)
		solve(market[i]);
	printf("%d\n", getv(S));
	
}

Compilation message (stderr)

salesman.cpp: In function 'void solve(std::vector<std::pair<int, int> >&)':
salesman.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<market.size(); ++i)
               ~^~~~~~~~~~~~~~
salesman.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<market.size(); ++i)
               ~^~~~~~~~~~~~~~
salesman.cpp:64:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i != market.size()-1)
      ~~^~~~~~~~~~~~~~~~~~
salesman.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<market.size(); ++i)
               ~^~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:74:6: warning: unused variable 'St' [-Wunused-variable]
  int St;
      ^~
salesman.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &N, &U, &D, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:78:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t, l, m; scanf("%d%d%d", &t, &l, &m);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100