oj.uz

답안 #138512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138512 2019-07-30T05:51:14 Z baluteshih Salesman (IOI09_salesman) C++14
100 / 100
 625 ms 16520 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 10488 KB Output is correct
2 Correct 14 ms 10488 KB Output is correct
3 Correct 14 ms 10488 KB Output is correct
4 Correct 15 ms 10488 KB Output is correct
5 Correct 18 ms 10616 KB Output is correct
6 Correct 35 ms 10744 KB Output is correct
7 Correct 74 ms 11236 KB Output is correct
8 Correct 138 ms 11760 KB Output is correct
9 Correct 206 ms 12280 KB Output is correct
10 Correct 293 ms 14072 KB Output is correct
11 Correct 390 ms 14088 KB Output is correct
12 Correct 490 ms 15352 KB Output is correct
13 Correct 480 ms 15360 KB Output is correct
14 Correct 593 ms 16420 KB Output is correct
15 Correct 504 ms 16504 KB Output is correct
16 Correct 625 ms 16504 KB Output is correct
17 Correct 13 ms 10488 KB Output is correct
18 Correct 13 ms 10488 KB Output is correct
19 Correct 14 ms 10488 KB Output is correct
20 Correct 15 ms 10488 KB Output is correct
21 Correct 16 ms 10588 KB Output is correct
22 Correct 18 ms 10620 KB Output is correct
23 Correct 17 ms 10616 KB Output is correct
24 Correct 18 ms 10616 KB Output is correct
25 Correct 114 ms 11764 KB Output is correct
26 Correct 214 ms 12920 KB Output is correct
27 Correct 326 ms 14588 KB Output is correct
28 Correct 418 ms 14752 KB Output is correct
29 Correct 482 ms 16520 KB Output is correct
30 Correct 486 ms 16504 KB Output is correct