#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const int MAXN = 500003, INF = 2*1e9;
//Global Variables
int N, U, D, S, dp[MAXN], t0D[4*MAXN+1], t0U[4*MAXN+1], dpU[4*MAXN+1], dpD[4*MAXN+1], pre[MAXN];
pair<int, pair<int, int> > fairs[MAXN]; /// (day, (location, profit) )
void updatedpU(int ind, int L, int R, int x, int v) {
if (x < L || R < x) return;
if (L == R) {
dpU[ind] = v;
return;
}
updatedpU(ind*2, L, (L+R)/2, x, v);
updatedpU(ind*2+1, (L+R)/2+1, R, x, v);
dpU[ind] = max(dpU[ind*2], dpU[ind*2+1]);
}
void updatedpD(int ind, int L, int R, int x, int v) {
if (x < L || R < x) return;
if (L == R) {
dpD[ind] = v;
return;
}
updatedpD(ind*2, L, (L+R)/2, x, v);
updatedpD(ind*2+1, (L+R)/2+1, R, x, v);
dpD[ind] = max(dpD[ind*2], dpD[ind*2+1]);
}
void updatet0D(int ind, int L, int R, int x, int v) {
if (x < L || R < x) return;
if (L == R) {
t0D[ind] = v;
return;
}
updatet0D(ind*2, L, (L+R)/2, x, v);
updatet0D(ind*2+1, (L+R)/2+1, R, x, v);
t0D[ind] = max(t0D[ind*2], t0D[ind*2+1]);
}
void updatet0U(int ind, int L, int R, int x, int v) {
if (x < L || R < x) return;
if (L == R) {
t0U[ind] = v;
return;
}
updatet0U(ind*2, L, (L+R)/2, x, v);
updatet0U(ind*2+1, (L+R)/2+1, R, x, v);
t0U[ind] = max(t0U[ind*2], t0U[ind*2+1]);
}
int querydpU(int ind, int L, int R, int oL, int oR) {
if (oR < L || R < oL) return -INF;
if (oL == 6 && oR == 6) w<< ind s L s R c dpU[ind]<<e;
if (oL <= L && R <= oR) return dpU[ind];
return max(querydpU(ind*2, L, (L+R)/2, oL, oR), querydpU(ind*2+1, (L+R)/2+1, R, oL, oR));
}
int querydpD(int ind, int L, int R, int oL, int oR) {
if (oR < L || R < oL) return -INF;
if (oL <= L && R <= oR) return dpD[ind];
return max(querydpD(ind*2, L, (L+R)/2, oL, oR), querydpD(ind*2+1, (L+R)/2+1, R, oL, oR));
}
int queryt0U(int ind, int L, int R, int oL, int oR) {
if (oR < L || R < oL) return -INF;
if (oL <= L && R <= oR) return t0U[ind];
return max(queryt0U(ind*2, L, (L+R)/2, oL, oR), queryt0U(ind*2+1, (L+R)/2+1, R, oL, oR));
}
int queryt0D(int ind, int L, int R, int oL, int oR) {
if (oR < L || R < oL) return -INF;
if (oL <= L && R <= oR) return t0D[ind];
return max(queryt0D(ind*2, L, (L+R)/2, oL, oR), queryt0D(ind*2+1, (L+R)/2+1, R, oL, oR));
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> U >> D >> S;
ffi cin >> fairs[i].a >> fairs[i].b.a >> fairs[i].b.b;
fairs[N] = mp(MAXN, mp(S, 0));
N++;
sort(fairs, fairs+N);
For (i, 0, MAXN) dp[i] = -INF;
For (i, 0, 4*MAXN+1) t0D[i] = t0U[i] = dpU[i] = dpD[i] = -INF;
dp[S] = 0;
updatedpU(1, 0, MAXN-1, S, -U*S);
updatedpD(1, 0, MAXN-1, S, D*S);
//w<< querydpU(1, 0, MAXN-1, 0, MAXN-1)<<e;
int i=0;
while (i < N) {
int k = i;
while (k+1 < N && fairs[k+1].a == fairs[i].a) k++;
/// fairs with the same day are i to k
/// update with pre values
if (i != 0) pre[i-1] = 0;
pre[i] = fairs[i].b.b;
For (l, i+1, k+1) pre[l] = pre[l-1] + fairs[l].b.b;
For (l, i, k+1) {
int loc = fairs[l].b.a;
int prel1 = 0;
if (l != 0) prel1 = pre[l-1];
int tdp0 = max(querydpU(1, 0, MAXN-1, loc, MAXN-1) + U*loc, querydpD(1, 0, MAXN-1, 0, loc) - D*loc);
//w<< loc s tdp0 c tdp0 + D*loc-prel1 s tdp0 - U*loc + pre[l]<<e;
//if (loc == S) w<<"at S" s querydpU(1, 0, MAXN-1, 6, 6) s tdp0<<e;
updatet0D(1, 0, MAXN-1, loc, tdp0 + D*loc-prel1);
updatet0U(1, 0, MAXN-1, loc, tdp0 - U*loc + pre[l]);
}
For (l, i, k+1) {
int loc = fairs[l].b.a;
int prel1 = 0;
if (l != 0) prel1 = pre[l-1];
dp[loc] = max(queryt0D(1, 0, MAXN-1, 0, loc) + pre[l] - D*loc, queryt0U(1, 0, MAXN-1, loc, MAXN-1) - prel1+ U*loc);
//w<< "dp" s loc s dp[loc] c queryt0D(1, 0, MAXN-1, 0, loc)<<e;
//if (loc == 6) w<< dp[loc]<<e;
updatedpU(1, 0, MAXN-1, loc, dp[loc]-U*loc);
//if (loc == 6) w<< dp[loc] s querydpU(1, 0, MAXN-1, S, MAXN-1)<<e;
updatedpD(1, 0, MAXN-1, loc, dp[loc]+D*loc);
}
/// reset values
For (l, i, k+1) {
int loc = fairs[l].b.a;
updatet0D(1, 0, MAXN-1, loc, -INF);
updatet0U(1, 0, MAXN-1, loc, -INF);
}
i = k+1;
}
//For (i, 0, MAXN) if (dp[i] != -INF) w<< i c dp[i]<<e;
w << dp[S]<<e;
}
Compilation message
salesman.cpp:86:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
33656 KB |
Output is correct |
| 2 |
Correct |
26 ms |
33656 KB |
Output is correct |
| 3 |
Correct |
27 ms |
33656 KB |
Output is correct |
| 4 |
Correct |
30 ms |
33656 KB |
Output is correct |
| 5 |
Correct |
37 ms |
33784 KB |
Output is correct |
| 6 |
Correct |
84 ms |
34296 KB |
Output is correct |
| 7 |
Correct |
186 ms |
35420 KB |
Output is correct |
| 8 |
Correct |
355 ms |
37080 KB |
Output is correct |
| 9 |
Correct |
505 ms |
38452 KB |
Output is correct |
| 10 |
Correct |
859 ms |
43180 KB |
Output is correct |
| 11 |
Correct |
986 ms |
43768 KB |
Output is correct |
| 12 |
Execution timed out |
1074 ms |
45760 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1082 ms |
46300 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1081 ms |
49828 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1084 ms |
49272 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1085 ms |
48820 KB |
Time limit exceeded |
| 17 |
Correct |
26 ms |
33656 KB |
Output is correct |
| 18 |
Correct |
27 ms |
33656 KB |
Output is correct |
| 19 |
Correct |
28 ms |
33656 KB |
Output is correct |
| 20 |
Correct |
31 ms |
33784 KB |
Output is correct |
| 21 |
Correct |
37 ms |
33704 KB |
Output is correct |
| 22 |
Correct |
36 ms |
33724 KB |
Output is correct |
| 23 |
Correct |
36 ms |
33784 KB |
Output is correct |
| 24 |
Correct |
37 ms |
33656 KB |
Output is correct |
| 25 |
Correct |
294 ms |
36608 KB |
Output is correct |
| 26 |
Correct |
554 ms |
39672 KB |
Output is correct |
| 27 |
Correct |
975 ms |
43640 KB |
Output is correct |
| 28 |
Execution timed out |
1082 ms |
44404 KB |
Time limit exceeded |
| 29 |
Execution timed out |
1067 ms |
47224 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1074 ms |
48536 KB |
Time limit exceeded |
