Submission #853021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
853021	2023-09-23T10:32:26 Z	denniskim	Salesman (IOI09_salesman)	C++17	100 / 100	885 ms	59732 KB

salesman

#include <bits/stdc++.h>
 
using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 987654321
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
 
ll n, U, D, S;
ll all, bll, cll;
vector<pll> vec[500010];
ll dp[500010];
ll nu[500010], maxx1[500010], maxx2[500010];
ll ans;
 
struct segtree
{
	ll seg[2000010];
	
	void init(ll no, ll s, ll e)
	{
		seg[no] = -INF;
		
		if(s == e)
			return;
		
		init(no << 1, s, (s + e) >> 1);
		init(no << 1 | 1, ((s + e) >> 1) + 1, e);
	}
	
	void update(ll no, ll s, ll e, ll w, ll v)
	{
		if(e < w || w < s)
			return;
		
		if(s == e)
		{
			seg[no] = v;
			return;
		}
		
		update(no << 1, s, (s + e) >> 1, w, v);
		update(no << 1 | 1, ((s + e) >> 1) + 1, e, w, v);
		
		seg[no] = max(seg[no << 1], seg[no << 1 | 1]);
	}
	
	ll query(ll no, ll s, ll e, ll l, ll r)
	{
		if(e < l || r < s || l > r)
			return -INF;
		
		if(l <= s && e <= r)
			return seg[no];
		
		return max(query(no << 1, s, (s + e) >> 1, l, r), query(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r));
	}
}segt1, segt2;
 
int main(void)
{
	fastio
	
	cin >> n >> U >> D >> S;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		cin >> all >> bll >> cll;
		vec[all].push_back({bll, cll});
	}
	
	segt1.init(1, 1, 500001);
	segt2.init(1, 1, 500001);
	segt1.update(1, 1, 500001, S, 0 + U * S);
	segt2.update(1, 1, 500001, S, 0 - D * S);
	
	for(ll i = 1 ; i <= 500001 ; i++)
	{
		if(vec[i].empty())
			continue;
		
		ll siz = (ll)vec[i].size();
		
      
		sort(vec[i].begin(), vec[i].end());
		reverse(vec[i].begin(), vec[i].end());
		vec[i].push_back({0, 0});
		reverse(vec[i].begin(), vec[i].end());
		vec[i].push_back({500002, 0});
		
		nu[0] = 0;
		maxx1[0] = -INF;
		maxx2[500002] = -INF;
		
		for(ll j = 1 ; j <= siz ; j++)
			nu[vec[i][j].fi] = nu[vec[i][j - 1].fi] + vec[i][j].se;
		
		ll gap = -INF;
		
		for(ll j = 1 ; j <= siz ; j++)
		{
			ll gap1 = segt1.query(1, 1, 500001, vec[i][j - 1].fi + 1, vec[i][j].fi - 1) - nu[vec[i][j - 1].fi];
			ll gap2 = gap + segt2.query(1, 1, 500001, vec[i][j - 1].fi + 1, vec[i][j].fi - 1);
			maxx1[vec[i][j].fi] = max(max(gap1, gap2), maxx1[vec[i][j - 1].fi]);
			gap = max(gap, (U + D) * vec[i][j].fi - nu[vec[i][j - 1].fi]);
		}
		
		gap = -INF;
		
		for(ll j = siz ; j >= 1 ; j--)
		{
			ll gap1 = segt2.query(1, 1, 500001, vec[i][j].fi + 1, vec[i][j + 1].fi - 1) + nu[vec[i][j].fi];
			ll gap2 = gap + segt1.query(1, 1, 500001, vec[i][j].fi + 1, vec[i][j + 1].fi - 1);
			maxx2[vec[i][j].fi] = max(max(gap1, gap2), maxx2[vec[i][j + 1].fi]);
			gap = max(gap, -(U + D) * vec[i][j].fi + nu[vec[i][j].fi]);
		}
		
		for(ll j = 1 ; j <= siz ; j++)
		{
			dp[vec[i][j].fi] = max(maxx1[vec[i][j].fi] + nu[vec[i][j].fi] - U * vec[i][j].fi, maxx2[vec[i][j].fi] + D * vec[i][j].fi - nu[vec[i][j - 1].fi]);
			segt1.update(1, 1, 500001, vec[i][j].fi, U * vec[i][j].fi + dp[vec[i][j].fi]);
			segt2.update(1, 1, 500001, vec[i][j].fi, dp[vec[i][j].fi] - D * vec[i][j].fi);
		}
	}
	
	for(ll i = 0 ; i <= 500002 ; i++)
	{
		if(i <= S)
			ans = max(ans, dp[i] - U * (S - i));
		else
			ans = max(ans, dp[i] - D * (i - S));
	}
	
	cout << ans;
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	31576 KB	Output is correct
2	Correct	9 ms	31320 KB	Output is correct
3	Correct	8 ms	31404 KB	Output is correct
4	Correct	12 ms	31640 KB	Output is correct
5	Correct	13 ms	31924 KB	Output is correct
6	Correct	35 ms	32684 KB	Output is correct
7	Correct	87 ms	34132 KB	Output is correct
8	Correct	163 ms	37176 KB	Output is correct
9	Correct	267 ms	39816 KB	Output is correct
10	Correct	397 ms	48408 KB	Output is correct
11	Correct	529 ms	48220 KB	Output is correct
12	Correct	731 ms	53996 KB	Output is correct
13	Correct	734 ms	53980 KB	Output is correct
14	Correct	815 ms	59732 KB	Output is correct
15	Correct	758 ms	59472 KB	Output is correct
16	Correct	885 ms	59648 KB	Output is correct
17	Correct	10 ms	31324 KB	Output is correct
18	Correct	8 ms	31580 KB	Output is correct
19	Correct	9 ms	31592 KB	Output is correct
20	Correct	10 ms	31576 KB	Output is correct
21	Correct	10 ms	31580 KB	Output is correct
22	Correct	12 ms	31656 KB	Output is correct
23	Correct	12 ms	31580 KB	Output is correct
24	Correct	13 ms	31580 KB	Output is correct
25	Correct	174 ms	32664 KB	Output is correct
26	Correct	266 ms	33556 KB	Output is correct
27	Correct	454 ms	34864 KB	Output is correct
28	Correct	525 ms	35884 KB	Output is correct
29	Correct	713 ms	36848 KB	Output is correct
30	Correct	595 ms	36548 KB	Output is correct