Submission #138455

#	Time	Username	Problem	Language	Result	Execution time	Memory
138455		baluteshih	Salesman (IOI09_salesman)	C++14	62 / 100	596 ms	25564 KiB

salesman

#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=500001;
pii seg[2000005];
int dp[500005];

void build(int l,int r,int rt)
{
	seg[rt]=MP(-INF,-INF);
	if(l==r) return;
	int m=l+r>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
}

void modify(int x,int l,int r,int rt,pii v)
{
	if(l==r)
		return seg[rt].F=max(seg[rt].F,v.F),seg[rt].S=max(seg[rt].S,v.S),void();
	int m=l+r>>1;
	if(x<=m) modify(x,l,m,rt<<1,v);
	else modify(x,m+1,r,rt<<1|1,v);
	seg[rt]=MP(max(seg[rt<<1].F,seg[rt<<1|1].F),max(seg[rt<<1].S,seg[rt<<1|1].S));
}

pii 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);
	auto a=query(L,R,l,m,rt<<1),b=query(L,R,m+1,r,rt<<1|1);
	return MP(max(a.F,b.F),max(a.S,b.S));
}

int main()
{jizz
	int n,u,d,s;
	cin >> n >> u >> d >> arr[0].pl;
	for(int i=1;i<=n;++i)
		cin >> arr[i].ti >> arr[i].pl >> arr[i].earn;
	build(1,MAXC,1),sort(arr+1,arr+n+1),modify(arr[0].pl,1,MAXC,1,MP(arr[0].pl*d,-arr[0].pl*u));
	for(int i=1;i<=n;++i)
	{
		dp[i]=max(query(1,arr[i].pl,1,MAXC,1).F-arr[i].pl*d,query(arr[i].pl,MAXC,1,MAXC,1).S+arr[i].pl*u)+arr[i].earn;
		modify(arr[i].pl,1,MAXC,1,MP(dp[i]+arr[i].pl*d,dp[i]-arr[i].pl*u));
	}
	cout << max(query(1,arr[0].pl,1,MAXC,1).F-arr[0].pl*d,query(arr[0].pl,MAXC,1,MAXC,1).S+arr[0].pl*u) << "\n";
}

Compilation message (stderr)

salesman.cpp: In function 'void build(int, int, int)':
salesman.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'void modify(int, int, int, int, pii)':
salesman.cpp:41:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'pii query(int, int, int, int, int)':
salesman.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
salesman.cpp: In function 'int main()':
salesman.cpp:60:12: warning: unused variable 's' [-Wunused-variable]
  int n,u,d,s;
            ^

• Subtask 1: 62 / 100