#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std ;
#define ff first
#define ss second
#define pb push_back
const int N = 5e5+2 ;
const int oo = 2e9+2 ;
struct fair {
int d, l, m ;
bool operator < ( const fair &e ) const {
return ( e.d == d ? e.l < l : d < e.d ) ;
}
};
fair fairs[N] ;
int mx[20*N][2] ;
int dp[N] ;
vector <int> ofT[N] ;
int best[N][2] ;
void build ( int l, int r, int node ) {
mx[node][0] = mx[node][1] = -oo ;
if ( l == r ) {
return ;
}
build ( l, (l+r)/2, node*2 ) ;
build ((l+r)/2+1, r, (node*2)+1 );
}
void update ( int l, int r, int a, int v, int flag, int node ) {
if ( l > a || r < a ) return ;
if ( l == a && r == a ) {
mx[node][flag] = max ( mx[node][flag], v ) ;
return;
}
update ( l, (l+r)/2, a, v, flag, node*2 ) ;
update ( (l+r)/2+1, r, a, v, flag, (node*2)+1 ) ;
mx[node][flag] = max ( mx[node*2][flag], mx[(node*2)+1][flag] ) ;
}
int query ( int l, int r, int a, int b, int flag, int node ) {
if ( a>r || b<l ) return -oo ;
if ( a <= l && r <= b ) {
return mx[node][flag] ;
}
int MX = max ( query (l,(l+r)/2, a, b,flag, node*2), query((l+r)/2+1,r,a,b,flag,(node*2)+1) ) ;
return MX ;
}
int n, u, d, s ;
void fun ( int i, int flag ) {
vector <pair <int,int> > X ;
int su = 0, sz = ofT[i].size() ;
for ( int j = 0 ; j < sz ; ++j ) {
X.pb ( make_pair(su,j) ) ;
su += fairs[ofT[i][j]].m - (d+u) * (fairs[ofT[i][min(sz-1,j+1)]].l - fairs[ofT[i][j]].l) ;
}
sort ( X.rbegin(), X.rend() ) ;
int l = 0 ;
su = 0;
for ( int j = 0 ; j < sz ; ++j ) {
while ( l <= X[j].ss ) {
best[ofT[i][l]][flag] = X[j].ff - su ;
su += (d+u) * (fairs[ofT[i][min(sz-1,l+1)]].l - fairs[ofT[i][l]].l) - fairs[ofT[i][l]].m ;
++l ;
}
}
}
int main() {
cin >> n >> d >> u >> s ;
for ( int i = 0 ; i < n ; ++ i ) {
cin >> fairs[i].d >> fairs[i].l >> fairs[i].m ;
}
sort ( fairs, fairs+n ) ;
for ( int i = 0 ; i < n ; ++i )
ofT[fairs[i].d].pb ( i ) ;
for ( int i = 0 ; i < N ; ++i ) {
fun ( i, 0 ) ;
reverse ( ofT[i].begin(), ofT[i].end() ) ;
fun ( i, 1 ) ;
reverse ( ofT[i].begin(), ofT[i].end() ) ;
}
build ( 0,N-1,1 ) ;
update ( 0, N-1, s, s*u, 0,1 ) ;
update ( 0, N-1, s, -s*d, 1,1) ;
for ( int i = N-1 ; i >= 0 ; --i ) {
vector <int> l1 ;
for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
l1.pb ( fairs[ofT[i][j]].m + best[ofT[i][j]][0] - fairs[ofT[i][j]].l * u + query (0,N-1,0,fairs[ofT[i][j]].l,0,1) ) ;
update (0,N-1,fairs[ofT[i][j]].l,l1.back()+fairs[ofT[i][j]].l*u,0,1) ;
}
reverse ( ofT[i].begin(), ofT[i].end() ) ;
for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
int l2 = fairs[ofT[i][j]].m + best[ofT[i][j]][1] + fairs[ofT[i][j]].l * d + query (0,N-1,fairs[ofT[i][j]].l,N-1,1,1) ;
dp[ofT[i][j]] = max ( l1[j], l2 ) ;
update (0,N-1,fairs[ofT[i][j]].l, l2 - fairs[ofT[i][j]].l*d,1,1) ;
}
for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
update(0,N-1,fairs[ofT[i][j]].l, dp[ofT[i][j]]+fairs[ofT[i][j]].l*u,0,1) ;
update(0,N-1,fairs[ofT[i][j]].l, dp[ofT[i][j]]-fairs[ofT[i][j]].l*d,1,1) ;
}
}
int ans = max (-s * u + query (0,N-1,0,s,0,1), d*s + query(0,N-1,s,N-1,1,1) ) ;
cout << ans << endl ;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:111:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
~~^~~~~~~~~~~~~~~
salesman.cpp:116:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
~~^~~~~~~~~~~~~~~
salesman.cpp:121:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
20352 KB |
Output is correct |
| 2 |
Correct |
24 ms |
20352 KB |
Output is correct |
| 3 |
Correct |
27 ms |
20352 KB |
Output is correct |
| 4 |
Correct |
34 ms |
20480 KB |
Output is correct |
| 5 |
Correct |
35 ms |
20736 KB |
Output is correct |
| 6 |
Correct |
86 ms |
21752 KB |
Output is correct |
| 7 |
Correct |
174 ms |
23928 KB |
Output is correct |
| 8 |
Correct |
342 ms |
27768 KB |
Output is correct |
| 9 |
Correct |
476 ms |
30840 KB |
Output is correct |
| 10 |
Correct |
844 ms |
41464 KB |
Output is correct |
| 11 |
Correct |
930 ms |
42360 KB |
Output is correct |
| 12 |
Correct |
1214 ms |
48428 KB |
Output is correct |
| 13 |
Correct |
1205 ms |
48632 KB |
Output is correct |
| 14 |
Correct |
1515 ms |
56696 KB |
Output is correct |
| 15 |
Correct |
1403 ms |
55716 KB |
Output is correct |
| 16 |
Correct |
1589 ms |
55944 KB |
Output is correct |
| 17 |
Incorrect |
24 ms |
20352 KB |
Output isn't correct |
| 18 |
Incorrect |
24 ms |
20352 KB |
Output isn't correct |
| 19 |
Incorrect |
26 ms |
20352 KB |
Output isn't correct |
| 20 |
Incorrect |
30 ms |
20352 KB |
Output isn't correct |
| 21 |
Incorrect |
29 ms |
20352 KB |
Output isn't correct |
| 22 |
Incorrect |
36 ms |
20608 KB |
Output isn't correct |
| 23 |
Incorrect |
34 ms |
20472 KB |
Output isn't correct |
| 24 |
Incorrect |
36 ms |
20608 KB |
Output isn't correct |
| 25 |
Incorrect |
283 ms |
24568 KB |
Output isn't correct |
| 26 |
Incorrect |
571 ms |
29112 KB |
Output isn't correct |
| 27 |
Incorrect |
911 ms |
35536 KB |
Output isn't correct |
| 28 |
Incorrect |
1038 ms |
36440 KB |
Output isn't correct |
| 29 |
Incorrect |
1305 ms |
41080 KB |
Output isn't correct |
| 30 |
Incorrect |
1399 ms |
43764 KB |
Output isn't correct |
