#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500009;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpi;
vpi mark[MAXN];
int n,u,d,s,uptree[2*MAXN],downtree[2*MAXN];
int query(int *arr,int l,int r)
{
int ans=-INF;
for(l+=MAXN,r+=MAXN;l<=r;l>>=1,r>>=1)
{
if(l&1) ans=max(ans,arr[l++]);
if(~r&1) ans=max(ans,arr[r--]);
}
return ans;
}
void update(int *arr,int x,int v)
{
x+=MAXN;
arr[x]=max(arr[x],v);
for(;x>1;x>>=1) arr[x>>1]=max(arr[x],arr[x^1]);
}
void updatep(int x,int v)
{
update(uptree,x,v-u*x);
update(downtree,x,v+d*x);
}
int realquery(int a)
{
return max(query(downtree,0,a)-d*a,query(uptree,a,MAXN-1)+u*a);
}
void markt(vpi &market)
{
if(market.size()==0) return;
sort(market.begin(),market.end());
vector<int> U,D;
int sz=market.size();
for(int i=0;i<sz;i++)
{
int temp=realquery(market[i].first);
U.push_back(temp),D.push_back(temp);
}
for(int i=0;i<sz;i++)
{
if(i!=0) D[i]=max(D[i],D[i-1]-d*(market[i].first-market[i-1].first));
D[i]+=market[i].second;
}
for(int i=sz-1;i>=0;i--)
{
if(i!=sz-1) U[i]=max(U[i],U[i+1]-u*(market[i+1].first-market[i].first));
U[i]+=market[i].second;
}
for(int i=0;i<sz;i++) updatep(market[i].first,max(U[i],D[i]));
}
int main()
{
scanf("%d %d %d %d",&n,&u,&d,&s);
for(int i=0,x,y,z;i<n;i++)
{
scanf("%d %d %d",&x,&y,&z);
mark[x].push_back(make_pair(y,z));
}
memset(uptree,0xc0,sizeof(uptree));
memset(downtree,0xc0,sizeof(downtree));
updatep(s,0);
for(int i=1;i<=500001;i++) markt(mark[i]);
return !printf("%d",realquery(s));
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:59:10: 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:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
19960 KB |
Output is correct |
2 |
Correct |
20 ms |
20076 KB |
Output is correct |
3 |
Correct |
25 ms |
20180 KB |
Output is correct |
4 |
Correct |
21 ms |
20180 KB |
Output is correct |
5 |
Correct |
23 ms |
20196 KB |
Output is correct |
6 |
Correct |
49 ms |
20764 KB |
Output is correct |
7 |
Correct |
93 ms |
21660 KB |
Output is correct |
8 |
Correct |
240 ms |
23228 KB |
Output is correct |
9 |
Correct |
234 ms |
27192 KB |
Output is correct |
10 |
Correct |
479 ms |
36676 KB |
Output is correct |
11 |
Correct |
512 ms |
42056 KB |
Output is correct |
12 |
Correct |
675 ms |
47140 KB |
Output is correct |
13 |
Correct |
681 ms |
47140 KB |
Output is correct |
14 |
Correct |
824 ms |
50240 KB |
Output is correct |
15 |
Execution timed out |
1012 ms |
50240 KB |
Time limit exceeded |
16 |
Correct |
996 ms |
50240 KB |
Output is correct |
17 |
Correct |
24 ms |
50240 KB |
Output is correct |
18 |
Correct |
26 ms |
50240 KB |
Output is correct |
19 |
Correct |
27 ms |
50240 KB |
Output is correct |
20 |
Correct |
28 ms |
50240 KB |
Output is correct |
21 |
Correct |
23 ms |
50240 KB |
Output is correct |
22 |
Correct |
31 ms |
50240 KB |
Output is correct |
23 |
Correct |
26 ms |
50240 KB |
Output is correct |
24 |
Correct |
27 ms |
50240 KB |
Output is correct |
25 |
Correct |
148 ms |
50240 KB |
Output is correct |
26 |
Correct |
305 ms |
50240 KB |
Output is correct |
27 |
Correct |
403 ms |
50240 KB |
Output is correct |
28 |
Correct |
498 ms |
50240 KB |
Output is correct |
29 |
Correct |
453 ms |
50240 KB |
Output is correct |
30 |
Correct |
448 ms |
50240 KB |
Output is correct |