oj.uz

답안 #94235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94235 2019-01-17T00:09:08 Z jhnah917 Salesman (IOI09_salesman) C++14
100 / 100
 739 ms 36044 KB 
#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 a, int b, int k=0, int l=0, int r=MAX_N){
    	if (b <= l || r <=a)return -1e9;
    	if (a<=l&&r<=b) return seg[k];
		return max(query(a,b,k*2+1,l,(l+r)/2), query(a,b,k*2+2,(l+r)/2,r));
	}
	
	void update(int k, int v) {
    	k += MAX_N-1;
    	seg[k] = v;
		while (k > 0) {
			k=(k-1)/2;
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
		}
	}
};
 
SegTree s1, s2;
vector<p> v[500005];
 
int n, u, d, s, t;
 
inline int get(int pos){
	return max(s1.query(0, pos)-d*pos, s2.query(pos, 500002)+u*pos);
}

inline void update(int pos, int dp){
	s1.update(pos, dp + d * pos);
	s2.update(pos, dp - u * pos);
}

void step(int i){
	int num = v[i].size();
	if(!num) return;
	vector<int> dpl, dpr;
	for(int j=0; j<num; j++){
		int tmp = get(v[i][j].first) + v[i][j].second;
		dpl.push_back(tmp); dpr.push_back(tmp);
	}
	for(int j=1; j<num; j++){
		dpl[j] = max(dpl[j], dpl[j-1] - d * (v[i][j].first - v[i][j-1].first) + v[i][j].second);
	}
	for(int j=num-2; j>=0; j--){
		dpr[j] = max(dpr[j], dpr[j+1] - u * (v[i][j+1].first - v[i][j].first) + v[i][j].second);
	}
	for(int j=0; j<num; j++){
		int big = max(dpl[j], dpr[j]);
		update(v[i][j].first, big);
	}
}
 
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});
		t = max(t, a);
	}
	v[0].push_back({s, 0});
	v[++t].push_back({s, 0});
	
	for(int i=0; i<=t; i++){
		sort(v[i].begin(), v[i].end());
	}
	
	s1.update(s, d*s);
	s2.update(s, -u*s);
	
	for(int i=1; i<=t; i++){
		step(i);
	}
	
	cout << get(s);
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 20216 KB Output is correct
2 Correct 16 ms 20216 KB Output is correct
3 Correct 16 ms 20344 KB Output is correct
4 Correct 17 ms 20344 KB Output is correct
5 Correct 20 ms 20472 KB Output is correct
6 Correct 48 ms 20856 KB Output is correct
7 Correct 89 ms 21880 KB Output is correct
8 Correct 168 ms 23500 KB Output is correct
9 Correct 221 ms 25080 KB Output is correct
10 Correct 376 ms 29688 KB Output is correct
11 Correct 448 ms 29688 KB Output is correct
12 Correct 541 ms 32760 KB Output is correct
13 Correct 559 ms 32860 KB Output is correct
14 Correct 671 ms 35960 KB Output is correct
15 Correct 739 ms 35960 KB Output is correct
16 Correct 711 ms 36044 KB Output is correct
17 Correct 16 ms 20220 KB Output is correct
18 Correct 15 ms 20344 KB Output is correct
19 Correct 16 ms 20344 KB Output is correct
20 Correct 17 ms 20340 KB Output is correct
21 Correct 17 ms 20348 KB Output is correct
22 Correct 19 ms 20344 KB Output is correct
23 Correct 19 ms 20344 KB Output is correct
24 Correct 20 ms 20344 KB Output is correct
25 Correct 103 ms 21368 KB Output is correct
26 Correct 211 ms 22776 KB Output is correct
27 Correct 296 ms 24804 KB Output is correct
28 Correct 358 ms 24900 KB Output is correct
29 Correct 533 ms 25208 KB Output is correct
30 Correct 469 ms 26644 KB Output is correct