Submission #169919

#	Time	Username	Problem	Language	Result	Execution time	Memory
169919		Retro3014	Salesman (IOI09_salesman)	C++17	70 / 100	1082 ms	58476 KiB

salesman

#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1000000000LL;
const int MAX_N = 500001;

int N;
ll U, D, S;
struct ST{
	ll t, l, m;
	bool operator <(const ST &a)const{
		if(t==a.t){
			return l<a.l;
		}
		return t<a.t;
	}
};
vector<ST> v;
struct SEG{
	struct NODE{
		int l, r;
		ll mx;
	};
	vector<NODE> seg;
	int SZ;
	void add(){seg.pb({-1, -1, -INFLL});}
	void Init(int x){
		add();
		SZ = x;
	}
	void Update(int x, int y, ll z){
		update(0, 1, SZ, x, y, z);
	}
	void update(int idx, int s, int e, int x, int y, ll z){
		if(x<=s && e<=y)	{
			seg[idx].mx = max(seg[idx].mx, z);
			return;
		}
		if(x>e || y<s)	return;
		if(seg[idx].l==-1){
			seg[idx].l = seg.size(); add();
		}
		if(seg[idx].r == -1){
			seg[idx].r = seg.size(); add();
		}
		update(seg[idx].l, s, (s+e)/2, x, y, z); update(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
	ll Mx(int x){
		return mx(0, 1, SZ, x);
	}
	ll mx(int idx, int s, int e, int k){
		if(idx==-1)	return -INFLL;
		if(s==e)	return seg[idx].mx;
		if(k<=(s+e)/2){
			return max(seg[idx].mx, mx(seg[idx].l, s, (s+e)/2, k));
		}else{
			return max(seg[idx].mx, mx(seg[idx].r, (s+e)/2+1, e, k));
		}
	}
}Seg1, Seg2;

vector<pair<ll, int> > vt;

ll get(ll idx){
	return max(Seg1.Mx((int)idx)+idx*U, Seg2.Mx((int)idx)-idx*D);
}
void Upd(ll idx, ll x){
	Seg1.Update(1, (int)idx, x-idx*U);
	Seg2.Update((int)idx, MAX_N, x+idx*D);
}

ll prv[MAX_N+1];

int main(){
	scanf("%d%lld%lld%lld", &N, &U, &D, &S);
	Seg1.Init(MAX_N); Seg2.Init(MAX_N);
	Upd(S, 0);
	for(int i=0; i<N; i++){
		ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
		v.pb({a, b, c});
	}
	sort(v.begin(), v.end());
	int s = 0, e = 0;
	while(s<v.size()){
		while(e+1<v.size() && v[e+1].t==v[s].t)	e++;
		if(s==e){
			Upd(v[s].l, get(v[s].l)+v[s].m);
		}else{
			for(int i=s; i<=e; i++)	prv[i] = get(v[i].l);
			for(int i=s; i<=e; i++){
				Seg2.Update((int)v[i].l, MAX_N, max(prv[i]+v[i].l*D, Seg2.Mx((int)v[i].l))+v[i].m);
			}
			for(int i=e; i>=s; i--){
				Seg1.Update(1, (int)v[i].l, max(prv[i]-v[i].l*U, Seg1.Mx((int)v[i].l))+v[i].m);
			}
			for(int i=s; i<=e; i++){
				Upd(v[i].l, get(v[i].l));
			}
		}
		s = e+1; e++;
	}
	cout<<get(S);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:104:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(s<v.size()){
        ~^~~~~~~~~
salesman.cpp:105:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e+1<v.size() && v[e+1].t==v[s].t) e++;
         ~~~^~~~~~~~~
salesman.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld%lld", &N, &U, &D, &S);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:99:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100