제출 #68703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68703		KLPP	Salesman (IOI09_salesman)	C++14	15 / 100	1076 ms	66560 KiB

salesman

#include<iostream>
#include<vector>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long int lld;
#define INF 1000000000000
#define MAXL 6000
int n,u,d,s;
lld DP[MAXL];
lld cost(int start,int end){
	if(start>end)return u*(start-end);
	return d*(end-start);
}
class ST{
	lld segtree[4000000];
	int N;
	public:
		void build(int a, int b, int node){
			segtree[node]=-INF;
			if(a==b)return;
			int mid=(a+b)/2;
			build(a,mid,2*node);
			build(mid+1,b,2*node+1);
		}
		void Build(int n){
			build(0,n-1,1);
			N=n;
		}
		void update(int pos,lld val, int a, int b, int node){//cout<<a<<" "<<b<<endl;
			if(a>pos || pos>b)return;
			if(a==b){
				segtree[node]=max(segtree[node],val);
				return;
			}
			int mid=(a+b)/2;
			update(pos,val,a,mid,2*node);
			update(pos,val,mid+1,b,2*node+1);
			segtree[node]=max(segtree[2*node],segtree[2*node+1]);
		}
		void Update(int pos,lld val){
			update(pos,val,0,N-1,1);
		}
		lld query(int x, int y, int a, int b, int node){
			if(b<x || a>y)return -INF;
			if(x<=a && b<=y)return segtree[node];
			int mid=(a+b)/2;
			lld p1=query(x,y,a,mid,2*node);
			lld p2=query(x,y,mid+1,b,2*node+1);
			return max(p1,p2);
		}
		lld Query(int x, int y){
			return query(x,y,0,N-1,1);
		}
};
int main(){
	scanf("%d %d %d %d",&n,&u,&d,&s);
	vector<pair<int,pair<int,lld> > >fairs;
	for(int i=0;i<n;i++){
		int time,l;
		lld s;
		scanf("%d %d %lld",&time,&l,&s);
		fairs.push_back(pair<int,pair<int,lld> >(time,pair<int,lld>(l,s)));
	}
	sort(fairs.begin(),fairs.end());
	for(int i=0;i<MAXL;i++)DP[i]=-INF;
	DP[s]=0;
	int prev=0;
	ST *s1=new ST();
	
	s1->Build(MAXL);
	//s1->Update(s,0);
	//cout<<s1->Query(0,MAXL-1)<<endl;
	ST *s2=new ST();
	s2->Build(MAXL);
	s1->Update(s,0-u*s);
	s2->Update(s,0+d*s);
	for(int i=0;i<=n;i++){
		if(i>0 && fairs[i].first!=fairs[i-1].first){
			for(int j=prev;j<i;j++){
				int l=fairs[j].second.first;
				/*for(int k=0;k<MAXL;k++){
					if(DP[k]!=-INF && DP[l]<DP[k]+fairs[j].second.second-cost(k,l) && k!=l){
						DP[l]=DP[k]+fairs[j].second.second-cost(k,l);
					}
				}*/
				DP[l]=max(DP[l],fairs[j].second.second+s2->Query(0,l-1)-d*l);
				//cout<<fairs[j].second.second+s1->Query(0,l-1)-u*l<<endl;
				DP[l]=max(DP[l],fairs[j].second.second+s1->Query(l+1,MAXL-1)+u*l);
				//cout<<fairs[j].second.second+s2->Query(l+1,MAXL-1)+d*l<<endl;
				s1->Update(l,DP[l]-u*l);
				s2->Update(l,DP[l]+d*l);
			}
			prev=i;
		}
	}
	lld ans=0;
	/*for(int i=0;i<n;i++){
		cout<<DP[fairs[i].second.first]<<" "<<fairs[i].first<<endl;	
	}cout<<endl;*/
	for(int i=0;i<MAXL;i++){
		ans=max(ans,DP[i]-cost(i,s));
	}cout<<ans<<endl;
	//cout<<cost(100,120)<<endl;
	


	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In function 'int main()':
salesman.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&n,&u,&d,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&time,&l,&s);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 100