Submission #138512

#	Time	Username	Problem	Language	Result	Execution time	Memory
138512		baluteshih	Salesman (IOI09_salesman)	C++14	100 / 100	625 ms	16520 KiB

salesman

#pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ET cout << "\n"
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define MEM memset(i,j,sizeof i)
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct mode
{
	int ti,pl,earn;
	bool operator<(const mode &a)const{
		if(ti==a.ti) return pl<a.pl;
		return ti<a.ti;
	}
}arr[500005];

const int INF=2e9,MAXC=500002;
int dp[500005],u,d;

struct node
{
	int dpu,dpd;
	node operator+(const node &a)const{
		return node{max(dpu,a.dpu),max(dpd,a.dpd)};
	}
}seg[2000005];

void build(int l,int r,int rt)
{
	if(l==r) 
		return seg[rt]=node{dp[l]-l*u,dp[l]+l*d},void();
	int m=l+r>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void modify(int x,int l,int r,int rt)
{
	if(l==r)
		return seg[rt]=node{dp[l]-l*u,dp[l]+l*d},void();
	int m=l+r>>1;
	if(x<=m) modify(x,l,m,rt<<1);
	else modify(x,m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

node query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&R>=r)
		return seg[rt];
	int m=l+r>>1;
	if(R<=m) return query(L,R,l,m,rt<<1);
	if(L>m) return query(L,R,m+1,r,rt<<1|1);
	return query(L,R,l,m,rt<<1)+query(L,R,m+1,r,rt<<1|1);
}

int main()
{jizz
	int n,ans=0;
	cin >> n >> u >> d >> arr[0].pl;
	for(int i=1;i<=n;++i)
		cin >> arr[i].ti >> arr[i].pl >> arr[i].earn;
	sort(arr+1,arr+n+1),fill(dp,dp+MAXC+1,-INF),dp[arr[0].pl]=0,build(1,MAXC,1);
	for(int i=1,j=1;i<=n;)
	{
		int sum=0;
		while(j<=n&&arr[i].ti==arr[j].ti) ++j;
		for(int k=i,L=-INF,tmp=-INF;k<j;++k)
		{
			if(k==i)
				tmp=query(1,arr[k].pl,1,MAXC,1).dpd;
			else
			{
				auto x=query(arr[k-1].pl,arr[k].pl,1,MAXC,1);
				tmp=max({tmp,x.dpu+L,x.dpd-sum});
			}
			L=max(L,arr[k].pl*(u+d)-sum),sum+=arr[k].earn;
			dp[arr[k].pl]=max(dp[arr[k].pl],tmp-arr[k].pl*d+sum);
		}
		for(int k=j-1,R=-INF,tmp=-INF;k>=i;--k)
		{
			if(k==j-1)
				tmp=query(arr[k].pl,MAXC,1,MAXC,1).dpu+sum;
			else
			{
				auto x=query(arr[k].pl,arr[k+1].pl,1,MAXC,1);
				tmp=max({tmp,x.dpd+R,x.dpu+sum});
			}
			R=max(R,-arr[k].pl*(u+d)+sum),sum-=arr[k].earn;
			dp[arr[k].pl]=max(dp[arr[k].pl],tmp+arr[k].pl*u-sum);
		}
		for(;i<j;++i)
			modify(arr[i].pl,1,MAXC,1);
	}
	for(int i=1;i<=arr[0].pl;++i)
		ans=max(ans,dp[i]-(arr[0].pl-i)*d);
	for(int i=arr[0].pl+1;i<=MAXC;++i)
		ans=max(ans,dp[i]-(i-arr[0].pl)*u);
	cout << ans << "\n";
}

Compilation message (stderr)

salesman.cpp: In function 'void build(int, int, int)':
salesman.cpp:41:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'void modify(int, int, int, int)':
salesman.cpp:50:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'node query(int, int, int, int, int)':
salesman.cpp:60:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

• Subtask 1: 100 / 100