Submission #166396

#	Time	Username	Problem	Language	Result	Execution time	Memory
166396		quocnguyen1012	Salesman (IOI09_salesman)	C++14	100 / 100	826 ms	36792 KiB

salesman

#include <bits/stdc++.h>

#define Task "SALES"

using namespace std;

struct Seg_Tree{
	vector<int>ST;
	void reset(int n){
		ST.resize(n*4+5);
		fill(begin(ST),end(ST),-1e9);
	}
	void upd(int id,int l,int r,int i,int v){
		if (l>i||r<i) return;
		if (l==r){
			ST[id]=max(ST[id],v);
			return;
		}
		int mid=(l+r)/2;
		upd(id*2,l,mid,i,v), upd(id*2+1,mid+1,r,i,v);
		ST[id]=max(ST[id*2],ST[id*2+1]);
	}
	int get_max(int id,int l,int r,int L,int R){
		if (l>R||L>r) {
			return -1e9;
		}
		if (L<=l&&r<=R) return ST[id];
		int mid=(l+r)/2;
		return max(get_max(id*2,l,mid,L,R),get_max(id*2+1,mid+1,r,L,R));
	}
}up,down;

struct rand_struct{
	int L,T,M;
	int best;
	
	int cur,base;
	bool operator <(const rand_struct &other ) const{
		if (T!=other.T) return T<other.T;
		else return L<other.L;
	}
};

const int maxn=5e5+5;

int N;
rand_struct a[maxn];
int U,D,S;

int cost (int i,int j){
	if (i>=j) return (i-j)*U;
	else return (j-i)*D;
}

int query(int i){
	int Down=down.get_max(1,1,maxn-4,a[i].L,maxn-4)+a[i].L*U+a[i].M;
	int Up=up.get_max(1,1,maxn-4,1,a[i].L)-a[i].L*D+a[i].M;
	return max(Up,Down);
}

void update (int i){
	down.upd(1,1,maxn-4,a[i].L,a[i].best-a[i].L*U);
	up.upd(1,1,maxn-4,a[i].L,a[i].best+a[i].L*D);
}

signed main(void){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if (fopen(Task".INP","r")){
		freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout);
	}
	
	up.reset(maxn),down.reset(maxn);
	cin >>N>>U>>D>>S;
	for (int i=1;i<=N;++i) cin>>a[i].T>>a[i].L>>a[i].M;
	a[0].L=S, a[0].T=-1;
	a[N+1].L=S, a[N+1].T=maxn-4;
	sort (a,a+2+N);
	update(0);
	for (int i=1;i<=N;++i){
		if (i==N||a[i].T!=a[i+1].T){
			a[i].best=query(i);
			///cerr<<a[i].best<<'\n';
			update(i);
		}
		else{ 
			int first=i;
			while(i<=N&&a[i].T==a[first].T) ++i;
			--i;
			int last=i;
			for (int j=first;j<=last;++j){
				a[j].base=query(j);
				a[j].best=a[j].base;
			}
			a[first].cur=a[first].base;
			for (int j=first+1;j<=last;++j){
				int val=a[j-1].cur-cost(a[j-1].L,a[j].L)+a[j].M;
				if (val>a[j].base){
					a[j].cur=val;
				}
				else a[j].cur=a[j].base;
				if (a[j].cur>a[j].best) a[j].best=a[j].cur;
			}
			a[last].cur=a[last].base;
			for (int j=last-1;j>=first;--j){
				int val=a[j+1].cur-cost (a[j+1].L,a[j].L)+a[j].M;
				if (val>a[j].base) a[j].cur=val;
				else a[j].cur=a[j].base;
				if (a[j].cur>a[j].best) a[j].best=a[j].cur;
			}
			for (int j=first;j<=last;++j) update(j);
		}
	}
	cout <<max(0,query(N+1));
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:69:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:69:41: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(Task".INP","r",stdin); freopen(Task".OUT","w",stdout);
                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100