제출 #861561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861561		8pete8	Salesman (IOI09_salesman)	C++14	18 / 100	645 ms	64152 KiB

salesman

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int long long
const int mxn=5e5,mx=5e6+10,inf=1e18,minf=-1e18;
int n,u,d,s;
vector<pii>day[mxn+110];
struct seg{
	int v[2*mxn+110];
	void init(){for(int i=0;i<=2*mxn+100;i++)v[i]=minf;}
	void update(int pos,int val){
		pos+=n;
		v[pos]=max(val,v[pos]);
		for(;pos>0;pos>>=1)v[pos>>1]=max(v[pos],v[pos^1]);
	}
	int qry(int l,int r){
		int ans=minf;
		for(l+=n,r+=n;l<=r;l>>=1,r>>=1){
			if(l&1)ans=max(ans,v[l++]);
			if(!(r&1))ans=max(ans,v[r--]);
		}
		return ans;
	}
}t[2];
int32_t main(){
	cin>>n>>u>>d>>s;
	vector<ppii>q(n);
	int mx=0;
	for(int i=0;i<n;i++)cin>>q[i].f>>q[i].s.f>>q[i].s.s,mx=max(mx,q[i].f);
	n=mxn;
	t[0].init();
	t[1].init();
	t[0].update(s,d*s);
	t[1].update(s,-u*s);
	sort(all(q));
	for(auto i:q)day[i.f].pb(i.s);
	for(int i=1;i<=mxn+5;i++){
		int mx2=minf,in=0;
		vector<int>v(day[i].size(),minf);
		for(auto j:day[i]){
			int g=max(t[0].qry(0,j.f)-(d*j.f),t[1].qry(j.f,mxn+5)+(u*j.f))+j.s;
			v[in]=max(g,mx2+j.s-(d*j.f));
			mx2=max(v[in]+(d*j.f),mx2);
			in++;
		}
		mx2=minf;
		reverse(all(day[i]));
		for(auto j:day[i]){
			in--;
			int g=max(t[0].qry(0,j.f)-(d*j.f),t[1].qry(j.f,mxn+5)+(u*j.f))+j.s;
			v[in]=max(g,mx2+j.s+(u*j.f));
			mx2=max(v[in]-(u*j.f),mx2);
		}
		for(int j=0;j<day[i].size();j++){
			t[0].update(day[i][j].f,v[j]+(d*day[i][j].f));
			t[1].update(day[i][j].f,v[j]-(u*day[i][j].f));
		}
	}
	cout<<max({t[0].qry(0,s)-(d*s),t[1].qry(s,mxn+1)+(u*s),0ll});
}
/*
4 5 3 100
2 80 100
5 125 130
4 75 150
3 120 110
*/

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

salesman.cpp: In function 'int32_t main()':
salesman.cpp:79:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int j=0;j<day[i].size();j++){
      |               ~^~~~~~~~~~~~~~

• Subtask 1: 18 / 100