| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 155436 |
2019-09-28T06:04:17 Z |
karma |
Salesman (IOI09_salesman) |
C++14 |
|
293 ms |
26168 KB |
#include<bits/stdc++.h>
#define pb emplace_back
#define ll long long
#define Task "sales"
using namespace std;
template<typename T> inline void Cin(T &x)
{
char c;
T sign = 1;
x = 0;
for (c = getchar(); c < '0' || c > '9'; c = getchar())
if (c == '-') sign = -1;
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}
const int N = int(5e5) + 7;
const ll oo = (ll)1e15;
struct TStore {
int t, l, m;
bool operator<(const TStore& o)const& {return t < o.t || (t == o.t && l < o.l);}
} sl[N];
struct TBIT {
vector<ll> t;
int sz;
void Init(int n) {sz = n, t.resize(n + 1); fill(t.begin(), t.end(), -oo);}
void Update(int x, ll val) {for(; x <= sz; x += (x & -x)) t[x] = max(t[x], val);}
ll Get(int x) {ll res = -oo; for(; x > 0; x -= (x & -x)) res = max(res, t[x]); return res;}
} bit, rev;
int n, s, MaxPos;
ll u, d, ud, f, g, cost[N], sum, costl, costx;
vector<ll> qu;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
if(fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
Cin(n, u, d, s); MaxPos = s;
for(int i = 1; i <= n; ++i) {
Cin(sl[i].t, sl[i].l, sl[i].m);
MaxPos = max(MaxPos, sl[i].l);
}
sort(sl + 1, sl + n + 1); sl[n + 1].t = int(1e6);
bit.Init(MaxPos), rev.Init(MaxPos);
bit.Update(s, d * s), rev.Update(MaxPos - s + 1, -u * s);
int j = 1;
for(int i = 1; i <= n; ) {
while(sl[i].t == sl[j].t && j <= n) ++j;
if(i == j - 1) {
f = max(bit.Get(sl[i].l) - d * sl[i].l, rev.Get(MaxPos - sl[i].l + 1) + u * sl[i].l) + sl[i].m;
bit.Update(sl[i].l, f + d * sl[i].l), rev.Update(MaxPos - sl[i].l + 1, f - u * sl[i].l);
} else {
costl = costx = -oo; sum = 0;
for(int k = i; k < j; ++k) { // x -> l -> r
cost[k] = max(bit.Get(sl[k].l) - d * sl[k].l, rev.Get(MaxPos - sl[k].l + 1) + u * sl[k].l);
costl = max(costl, sl[k].l * (d + u) - sum);
sum += sl[k].m;
costx = max(costx, costl + cost[k] - sl[k].l * u);
f = costx - sl[k].l * d + sum;
qu.pb(f);
}
costl = costx = -oo; sum = 0;
for(int k = j - 1; k >= i; --k) { // x -> r -> l
costl = max(costl, -sl[k].l * (u + d) - sum);
sum += sl[k].m;
costx = max(costx, cost[k] + costl + sl[k].l * d);
f = costx + sl[k].l * u + sum;
bit.Update(sl[k].l, f + d * sl[k].l), rev.Update(MaxPos - sl[k].l + 1, f - u * sl[k].l);
bit.Update(sl[k].l, qu.back() + d * sl[k].l), rev.Update(MaxPos - sl[k].l + 1, qu.back() - u * sl[k].l);
qu.pop_back();
}
}
i = j;
}
cout << max(max(bit.Get(s) - d * s, rev.Get(MaxPos - s + 1) + u * s), 0ll);
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".inp", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
508 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Correct |
3 ms |
376 KB |
Output is correct |
| 5 |
Correct |
4 ms |
504 KB |
Output is correct |
| 6 |
Correct |
20 ms |
8952 KB |
Output is correct |
| 7 |
Correct |
36 ms |
9592 KB |
Output is correct |
| 8 |
Correct |
65 ms |
11128 KB |
Output is correct |
| 9 |
Correct |
86 ms |
12408 KB |
Output is correct |
| 10 |
Correct |
151 ms |
16504 KB |
Output is correct |
| 11 |
Correct |
178 ms |
17144 KB |
Output is correct |
| 12 |
Correct |
216 ms |
18936 KB |
Output is correct |
| 13 |
Correct |
221 ms |
19260 KB |
Output is correct |
| 14 |
Correct |
291 ms |
23064 KB |
Output is correct |
| 15 |
Correct |
245 ms |
22160 KB |
Output is correct |
| 16 |
Correct |
274 ms |
22136 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
3 ms |
532 KB |
Output is correct |
| 21 |
Correct |
3 ms |
504 KB |
Output is correct |
| 22 |
Correct |
4 ms |
636 KB |
Output is correct |
| 23 |
Correct |
5 ms |
632 KB |
Output is correct |
| 24 |
Correct |
5 ms |
636 KB |
Output is correct |
| 25 |
Correct |
63 ms |
11640 KB |
Output is correct |
| 26 |
Correct |
121 ms |
15224 KB |
Output is correct |
| 27 |
Correct |
200 ms |
20208 KB |
Output is correct |
| 28 |
Correct |
230 ms |
20852 KB |
Output is correct |
| 29 |
Correct |
273 ms |
24696 KB |
Output is correct |
| 30 |
Correct |
293 ms |
26168 KB |
Output is correct |
