Submission #94224

#	Time	Username	Problem	Language	Result	Execution time	Memory
94224		jhnah917	Salesman (IOI09_salesman)	C++14	0 / 100	538 ms	66560 KiB

salesman

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

const int MAX_N = 1<<19;

struct SegTree {
	int seg[MAX_N*2-1];
	SegTree() {
		for(int i=0; i<MAX_N*2-1; i++) seg[i] = -1e9;
	}
	
	int query(int s, int e){
        s += MAX_N, e += MAX_N;
        int r = -1e9;
        while(s < e){
            if(s%2 == 1) r = max(r,seg[s++]);
            if(e%2 == 0) r = max(r,seg[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = max(r,seg[s]);
        return r;
    }
	
	void update(int x, int v){
        x += MAX_N;
        seg[x] = max(seg[x],v);
        while(x > 1){
            x >>= 1;
            seg[x] = max(seg[2*x], seg[2*x+1]);
        }
    }
};

SegTree s1, s2;
vector<p> v[500050];
vector<int> dpl[500050], dpr[500050];
int n, u, s, d;

void update(int i, int j){
	s1.update(v[i][j].first, max(dpl[i][j], dpr[i][j]) + d * v[i][j].first);
	s2.update(v[i][j].first, max(dpl[i][j], dpr[i][j]) - u * v[i][j].first);
}

int get1(int i, int j){
	int ret = -1e9;
	if(j-1 >= 0) ret = dpl[i][j-1] - d * (v[i][j].first - v[i][j-1].first) + v[i][j].second;
	int t1 = s1.query(0, v[i][j].first) - d*v[i][j].first + v[i][j].second;
	int t2 = s2.query(v[i][j].first, 500001) + u*v[i][j].first + v[i][j].second;
	
	return max({ret, t1, t2});
}

int get2(int i, int j){
	int ret = -1e9;
	if(j+1 < v[i].size()) ret = dpr[i][j+1] - u * (v[i][j+1].first - v[i][j].first) + v[i][j].second;
	int t1 = s1.query(0, v[i][j].first) - d*v[i][j].first + v[i][j].second;
	int t2 = s2.query(v[i][j].first, 500001) + u*v[i][j].first + v[i][j].second;
	
	return max({ret, t1, t2});
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> u >> d >> s;
	
	for(int i=0; i<n; i++){
		int a, b, c; cin >> a >> b >> c;
		v[a].push_back({b, c});
	}
	v[0].push_back({s, 0});
	v[500001].push_back({s, 0});
	for(int i=0; i<=500001; i++){
		dpl[i].resize(v[i].size()), dpr[i].resize(v[i].size());
		sort(v[i].begin(), v[i].end());
	}
	
	dpl[0][0] = dpr[0][0] = 0;
	update(0, 0);
	for(int i=1; i<=n+1; i++){
		for(int j=0; j<v[i].size(); j++){
			dpl[i][j] = get1(i, j);
			dpr[i][j] = get2(i, j);
		}
		for(int j=0; j<v[i].size(); j++){
			update(i, j);
		}
	}
	
	cout << max(dpl[n+1][0], dpr[n+1][0]);
}

Compilation message (stderr)

salesman.cpp: In function 'int get2(int, int)':
salesman.cpp:58:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(j+1 < v[i].size()) ret = dpr[i][j+1] - u * (v[i][j+1].first - v[i][j].first) + v[i][j].second;
     ~~~~^~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:83:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v[i].size(); j++){
                ~^~~~~~~~~~~~
salesman.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v[i].size(); j++){
                ~^~~~~~~~~~~~

• Subtask 1: 0 / 100