Submission #120603

#	Time	Username	Problem	Language	Result	Execution time	Memory
120603		nvmdava	Salesman (IOI09_salesman)	C++17	37 / 100	1084 ms	28408 KiB

salesman

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

int n, d, u, s;

struct Plane{
	multiset<pair<int, int> > in;
	
	int insert(int loc, int val){
		auto it = in.insert({loc, val});
		it++;
		while(it != in.end() && it -> ss <= val - (it -> ff - loc) * d) it = in.erase(it);
		it--;
		while(it != in.begin() && (--it) -> ss <= val - (loc - it -> ff) * u) it = in.erase(it);
		return val;
	}
	
	int query(int loc){
		auto it = lower_bound(in.begin(), in.end(), loc, [ ](const pair<int, int> lhs, const int rhs){
			return rhs > lhs.ff;	
		});
		int val1, val2;
		val2 = (it == in.end() ? -2000000000 : it -> ss - (it -> ff - loc) * u);
		val1 = (it == in.begin() ? -2000000000 : (--it) -> ss - (loc - it -> ff) * d);
		return max(val1, val2);
	}
	void print(){
		for(auto x : in){
			cout<<x.ff<<' '<<x.ss<<'\n';
		}
		cout<<'\n';
	}
} s1, s2;

vector<pair<int, int> > fair[500005];
vector<pair<int, int> > tmp1, tmp2;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int res = 0;
	int n, s;
	cin>>n>>u>>d>>s;
	for(int i = 1; i <= n; i++){
		int t, l, m;
		cin>>t>>l>>m;
		fair[t].push_back({l, m});
	}
	
	s1.insert(s, 0);
	s2.insert(s, 0);
	
	for(int i = 1; i <= 500000; i++){
		int sz = fair[i].size();
		tmp1.clear();
		tmp2.clear();
		sort(fair[i].begin(), fair[i].end());
		for(int j = 0; j < sz; j++){
			tmp1.push_back({fair[i][j].ff, s1.insert(fair[i][j].ff, fair[i][j].ss + s1.query(fair[i][j].ff))});
			tmp2.push_back({fair[i][sz - 1 - j].ff, s2.insert(fair[i][sz - 1 - j].ff, fair[i][sz - j - 1].ss + s2.query(fair[i][sz - j - 1].ff))});
		}
		for(int j = 0; j < sz; j++){
			s2.insert(tmp1[j].ff, tmp1[j].ss);
			s1.insert(tmp2[j].ff, tmp2[j].ss);
		}
	}
	cout<<s1.query(s);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:43:6: warning: unused variable 'res' [-Wunused-variable]
  int res = 0;
      ^~~

• Subtask 1: 37 / 100