Submission #120590

#	Time	Username	Problem	Language	Result	Execution time	Memory
120590		nvmdava	Salesman (IOI09_salesman)	C++17	25 / 100	1090 ms	36856 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;
	
	void 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);
	}
	
	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);
	}
} s1, s2;

vector<pair<int, int> > fair[500005];

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);
	for(int i = 1; i <= 500000; i++){
		for(auto& x : fair[i]){
			s1.insert(x.ff, s1.query(x.ff) + x.ss);
		}
	}
	cout<<s1.query(s);
}

Compilation message (stderr)

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

• Subtask 1: 25 / 100