#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "SALES"
#define int ll
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
//typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll inf = -1e18;
const int maxn = 5e5 + 5;
vector<ii> a[maxn];
int n,u,d,s;
int dp[maxn];
int dp1[maxn];
int read(){
int x = 0;
char ch;
for(ch = getchar() ; ch > '9' || ch < '0' ; ch = getchar());
for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = x * 10 + ch - '0';
return x;
}
struct BIT{
int bit[maxn];
BIT(){fill_n(bit,maxn,inf);};
void update(int x , bool type , int val){
if(type == 1){
for( ; x > 0 ; x &= x - 1){
if(val != inf)bit[x] = max(bit[x] , val);
else bit[x] = inf;
}
}else{
for( ; x < maxn ; x += x & -x){
if(val != inf)bit[x] = max(bit[x] , val);
else bit[x] = inf;
}
}
}
int query(int x , bool type){
int res = inf;
if(type == 0){
for( ; x > 0 ; x &= x - 1){
res = max(res , bit[x]);
}
}else{
for( ; x < maxn ; x += x & -x){
res = max(res , bit[x]);
}
}
return res;
}
}data[4];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
n = read();u = read();d = read();s = read();
for(int i = 1 ; i <= n ; ++i){
int time = read(), pos = read(), profit = read();
a[time].pb(mp(pos , profit));
}
fill_n(dp,maxn,inf);
fill_n(dp1,maxn,inf);
dp[s] = 0;dp1[s] = 0;
a[0].pb(mp(s , 0));
a[maxn - 1].pb(mp(s , 0));
data[0].update(s , 0 , s * d);
data[1].update(s , 1 , - s * u);
for(int i = 0 ; i < maxn ; ++i){
sort(a[i].begin(),a[i].end());
for(int j = 1 ; j < (int)a[i].size() ; ++j){
a[i][j].second += a[i][j - 1].second;
}
for(int j = 0 ; j < (int)a[i].size() ; ++j){
ii c = a[i][j];
int sum = (j == 0 ? 0 : a[i][j - 1].second);
dp1[c.first] = max(data[0].query(c.first , 0) - d * c.first , data[1].query(c.first , 1) + u * c.first);
data[2].update(c.first , 0 , dp1[c.first] + d * c.first - sum);
data[3].update(c.first , 1 , dp1[c.first] - u * c.first + c.second);
}
for(int j = 0 ; j < (int)a[i].size() ; ++j){
ii c = a[i][j];
int sum = (j == 0 ? 0 : a[i][j - 1].second);
dp[c.first] = max(data[2].query(c.first , 0) - d * c.first + c.second , data[3].query(c.first , 1) + u * c.first - sum);
dp[c.first] = max({dp[c.first] , data[0].query(c.first , 0) + c.second - sum - d * c.first ,
data[1].query(c.first , 1) + c.second - sum + u * c.first});;
}
for(int j = 0 ; j < (int)a[i].size() ; ++j){
ii c = a[i][j];
data[0].update(c.first , 0 , dp[c.first] + d * c.first);
data[1].update(c.first , 1 , dp[c.first] - u * c.first);
data[2].update(c.first , 0 , inf);
data[3].update(c.first , 1 , inf);
}
}
cout << max(dp[s],0ll);
return 0;
//
}
Compilation message
salesman.cpp: In function 'int32_t main()':
salesman.cpp:70:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT", "w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
35576 KB |
Output is correct |
2 |
Correct |
33 ms |
35592 KB |
Output is correct |
3 |
Correct |
34 ms |
35576 KB |
Output is correct |
4 |
Correct |
34 ms |
35576 KB |
Output is correct |
5 |
Correct |
36 ms |
35704 KB |
Output is correct |
6 |
Correct |
57 ms |
36476 KB |
Output is correct |
7 |
Correct |
115 ms |
37496 KB |
Output is correct |
8 |
Correct |
163 ms |
39000 KB |
Output is correct |
9 |
Correct |
213 ms |
40568 KB |
Output is correct |
10 |
Correct |
370 ms |
45388 KB |
Output is correct |
11 |
Correct |
457 ms |
45392 KB |
Output is correct |
12 |
Correct |
686 ms |
48524 KB |
Output is correct |
13 |
Correct |
548 ms |
48584 KB |
Output is correct |
14 |
Correct |
739 ms |
51688 KB |
Output is correct |
15 |
Correct |
666 ms |
51724 KB |
Output is correct |
16 |
Correct |
650 ms |
51708 KB |
Output is correct |
17 |
Correct |
42 ms |
35576 KB |
Output is correct |
18 |
Correct |
34 ms |
35740 KB |
Output is correct |
19 |
Correct |
34 ms |
35576 KB |
Output is correct |
20 |
Correct |
34 ms |
35704 KB |
Output is correct |
21 |
Correct |
34 ms |
35728 KB |
Output is correct |
22 |
Correct |
36 ms |
35704 KB |
Output is correct |
23 |
Correct |
35 ms |
35704 KB |
Output is correct |
24 |
Correct |
39 ms |
35744 KB |
Output is correct |
25 |
Correct |
110 ms |
38008 KB |
Output is correct |
26 |
Correct |
188 ms |
40276 KB |
Output is correct |
27 |
Correct |
255 ms |
42940 KB |
Output is correct |
28 |
Correct |
307 ms |
43496 KB |
Output is correct |
29 |
Correct |
345 ms |
45348 KB |
Output is correct |
30 |
Correct |
421 ms |
46040 KB |
Output is correct |