oj.uz

Submission #124761

# Submission time Handle Problem Language Result Execution time Memory
124761 2019-07-03T21:56:18 Z arthurconmy Salesman (IOI09_salesman) C++14
62 / 100
 529 ms 27640 KB 
// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define pb push_back
#define ff first
#define ss second
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)

const ll NEG_INF = -1e18;
ll n,u,d,s;
tuple<int,int,int> fairs[500001]; // keep it int for space reasons
ll st[2][1048576]; // first is up, second is down monkaS for memory again!
ll dp[500001];

ll query(int l, int r, int tree)
{
	ll ans=NEG_INF;
	l+=524288;
	r+=524288;
	l--;
	r--;

	while(l<=r) // we know there's inequality in the case of the query RMQ(i,i)
	{
		if(l%2 == 1)
		{
			ans=max(ans,st[tree][l++]);
		}

		if(r%2 == 0)
		{
			ans=max(ans,st[tree][r--]);
		}

		l/=2;
		r/=2;
	}

	return ans;
}

void update(int pos, ll new_val, int tree)
{
	pos+=524288;
	pos--;
	st[tree][pos]=max(st[tree][pos],new_val);
	//cout << st[tree][pos] << endl;
	pos/=2;

	while(pos>0)
	{
		st[tree][pos] = max(st[tree][pos+pos],st[tree][pos+pos+1]);
		pos/=2;
	}
}

int main()
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	REP(i,0,1)
	{
		REP(j,0,1048575)
		{
			st[i][j]=NEG_INF;
		}
	}

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>u>>d>>s;

	// vector<tuple<int,int,int>> fairs;

	REP(i,1,n)
	{
		int t,l,m;
		cin>>t>>l>>m;
		fairs[i]={t,l,m};
	}

	sort(fairs+1,fairs+n+1);

	REP(i,1,n)
	{
		// cout << get<0>(fairs[i]) << " " << get<1>(fairs[i]) << " " << get<2>(fairs[i]) << endl;

		ll pos_cur = ll(get<1>(fairs[i]));
		ll prof_cur = ll(get<2>(fairs[i]));

		dp[i]=prof_cur;
		if(pos_cur>=s) dp[i]-=d*(pos_cur-s); // downstream
		else dp[i]-=u*(s-pos_cur);           // upstream. Yes this is the other way around to below

		// UPSTREAM QUERY

		dp[i]=max(dp[i],prof_cur + u*pos_cur + query(pos_cur,500000,0));

		// DOWNSTREAM QUERY

		dp[i]=max(dp[i],prof_cur - d*pos_cur + query(1,pos_cur,1));

		// UPSTREAM UPDATE

		update(int(pos_cur),dp[i]-u*pos_cur,0); // do we update with the DP value? Probably
		// if(i==1) cout << query(1,500000,0) << endl;

		// UPSTREAM UPDATE

		update(int(pos_cur),dp[i]+d*pos_cur,1);

		// cout << i << " " << dp[i] << endl;
	}

	ll ans=0;

	REP(i,1,n)
	{
		ll cur_pos = ll(get<1>(fairs[i]));
		ll cur_ans=dp[i];

		if(cur_pos>=s) cur_ans-=u*(cur_pos-s); // downstream
		else cur_ans-=d*(s-cur_pos); 

		ans=max(ans,cur_ans);  
	}

	cout << ans << endl;
}

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16760 KB Output is correct
2 Correct 15 ms 16760 KB Output is correct
3 Correct 15 ms 16632 KB Output is correct
4 Correct 16 ms 16760 KB Output is correct
5 Correct 18 ms 16888 KB Output is correct
6 Correct 36 ms 17528 KB Output is correct
7 Correct 69 ms 18680 KB Output is correct
8 Correct 122 ms 19976 KB Output is correct
9 Correct 164 ms 20856 KB Output is correct
10 Correct 313 ms 23544 KB Output is correct
11 Correct 334 ms 23644 KB Output is correct
12 Correct 439 ms 25464 KB Output is correct
13 Correct 430 ms 25540 KB Output is correct
14 Correct 524 ms 26952 KB Output is correct
15 Correct 454 ms 27592 KB Output is correct
16 Correct 529 ms 27492 KB Output is correct
17 Correct 15 ms 16760 KB Output is correct
18 Incorrect 15 ms 16760 KB Output isn't correct
19 Incorrect 15 ms 16760 KB Output isn't correct
20 Incorrect 17 ms 16888 KB Output isn't correct
21 Incorrect 17 ms 16888 KB Output isn't correct
22 Incorrect 18 ms 16888 KB Output isn't correct
23 Incorrect 18 ms 16888 KB Output isn't correct
24 Incorrect 18 ms 16956 KB Output isn't correct
25 Incorrect 110 ms 20088 KB Output isn't correct
26 Incorrect 199 ms 21880 KB Output isn't correct
27 Incorrect 370 ms 24684 KB Output isn't correct
28 Incorrect 354 ms 24568 KB Output isn't correct
29 Incorrect 456 ms 27640 KB Output isn't correct
30 Incorrect 440 ms 27480 KB Output isn't correct