#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define D(x) cerr << #x << " is " << (x) << "\n";
#define ld long double
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=5e5+5;
struct fair{
int t,l,m;
};
bool operator<(fair a,fair b){
if(a.t!=b.t)
return a.t<b.t;
if(a.l!=b.l)
return a.l<b.l;
return a.m<b.m;
}
vector<fair> f;
vector<int> r(N);
int n,u,d,s;
int getDist(int a,int b){
if(a<b)
return b*d-a*d;
return a*u-b*u;
}
struct segTree{
vector<int> mx;
segTree(){mx.resize(4*N,INT_MIN/2);}
void sett(int pos,int x,int l=0,int r=N-1,int i=1){
if(l==r){
assert(l==pos);
mx[i]=x;
return;
}
int m=(l+r)>>1;
if(pos<=m)
sett(pos,x,l,m,2*i);
else
sett(pos,x,m+1,r,2*i+1);
mx[i]=max(mx[2*i],mx[2*i+1]);
}
int get(int qs,int qe,int l=0,int r=N-1,int i=1){
if(qs>r||qe<l)
return INT_MIN/2;
if(qs<=l&&qe>=r)
return mx[i];
int m=(l+r)>>1;
int sol= max(get(qs,qe,l,m,2*i),get(qs,qe,m+1,r,2*i+1));
return sol;
}
}up,down;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
n=5e5;
u=d=s=1;
scanf("%i %i %i %i",&n,&u,&d,&s);
f.resize(n+1);
for(int i=1;i<=n;i++)
//f[i].t=5,f[i].l=1,f[i].m=4000;
scanf("%i %i %i",&f[i].t,&f[i].l,&f[i].m);
sort(all(f));
f.pb({0,0,0});
for(int i=n;i>=0;i--)
if(f[i].t==f[i+1].t)
r[i]=r[i+1];
else
r[i]=i;
up.sett(s,d*s);
down.sett(s,-u*s);
for(int i=1;i<=n;i++){
vector<int> dp(r[i]-i+1),dp2(r[i]-i+1),dp3(r[i]-i+1);
for(int j=i;j<=r[i];j++)
dp[j-i]=max(up.get(1,f[j].l)-f[j].l*d,down.get(f[j].l,N-1)+f[j].l*u)+f[j].m;
for(int j=i;j<=r[i];j++){
dp2[j-i]=dp[j-i];
if(j!=i)
dp2[j-i]=max(dp2[j-i],dp2[j-i-1]-getDist(f[j-1].l,f[j].l)+f[j].m);
}
for(int j=r[i];j>=i;j--){
dp3[j-i]=dp[j-i];
if(j!=r[i])
dp3[j-i]=max(dp3[j-i],dp3[j-i+1]-getDist(f[j+1].l,f[j].l)+f[j].m);
dp[j-i]=max({dp2[j-i],dp3[j-i]});
}
for(int j=i;j<=r[i];j++)
up.sett(f[j].l,dp[j-i]+d*f[j].l),down.sett(f[j].l,dp[j-i]-u*f[j].l);
i=r[i];
}
int sol=max(up.get(1,s)-s*d,down.get(s,N-1)+s*u);
sol=max(sol,0);
printf("%i\n",sol);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i %i",&n,&u,&d,&s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&f[i].t,&f[i].l,&f[i].m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
18040 KB |
Output is correct |
| 2 |
Correct |
18 ms |
17912 KB |
Output is correct |
| 3 |
Correct |
18 ms |
18040 KB |
Output is correct |
| 4 |
Correct |
25 ms |
18040 KB |
Output is correct |
| 5 |
Correct |
23 ms |
18040 KB |
Output is correct |
| 6 |
Correct |
50 ms |
18424 KB |
Output is correct |
| 7 |
Correct |
107 ms |
19192 KB |
Output is correct |
| 8 |
Correct |
193 ms |
20344 KB |
Output is correct |
| 9 |
Correct |
311 ms |
21504 KB |
Output is correct |
| 10 |
Correct |
459 ms |
25080 KB |
Output is correct |
| 11 |
Correct |
548 ms |
24952 KB |
Output is correct |
| 12 |
Correct |
727 ms |
27384 KB |
Output is correct |
| 13 |
Correct |
711 ms |
27256 KB |
Output is correct |
| 14 |
Correct |
886 ms |
29688 KB |
Output is correct |
| 15 |
Correct |
682 ms |
29692 KB |
Output is correct |
| 16 |
Correct |
906 ms |
29688 KB |
Output is correct |
| 17 |
Correct |
15 ms |
17784 KB |
Output is correct |
| 18 |
Correct |
22 ms |
18040 KB |
Output is correct |
| 19 |
Correct |
19 ms |
17912 KB |
Output is correct |
| 20 |
Correct |
26 ms |
18040 KB |
Output is correct |
| 21 |
Correct |
20 ms |
18040 KB |
Output is correct |
| 22 |
Correct |
23 ms |
18040 KB |
Output is correct |
| 23 |
Correct |
23 ms |
18040 KB |
Output is correct |
| 24 |
Correct |
23 ms |
18040 KB |
Output is correct |
| 25 |
Correct |
149 ms |
20216 KB |
Output is correct |
| 26 |
Correct |
281 ms |
22776 KB |
Output is correct |
| 27 |
Correct |
465 ms |
26232 KB |
Output is correct |
| 28 |
Correct |
527 ms |
26212 KB |
Output is correct |
| 29 |
Correct |
671 ms |
29788 KB |
Output is correct |
| 30 |
Correct |
657 ms |
29624 KB |
Output is correct |
