# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
254824 | karma | Salesman (IOI09_salesman) | C++14 | 278 ms | 18672 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
/// f(r) = max sum[r] - L[r] * d - sum[l - 1] + L[l] * d + cost[l]
for(int k = i; k < j; ++k) { // x -> l -> r, l < r -> * d
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, l > r -> * u
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);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |