# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
100787 | Alexa2001 | Salesman (IOI09_salesman) | C++17 | 1072 ms | 39544 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int lim = 5e5 + 2, Nmax = 5e5 + 10, inf = 2e9;
int dp[Nmax], x[Nmax], p[Nmax], come[Nmax];
int n, U, D;
vector<int> event[Nmax];
class AIB
{
int a[Nmax];
int ub(int x) { return (x&(-x)); }
public:
void init()
{
int i;
for(i=0; i<=lim; ++i) a[i] = -inf;
}
int query(int pos)
{
int ans = -inf;
for(; pos; pos-=ub(pos)) ans = max(ans, a[pos]);
return ans;
}
void update(int pos, int val)
{
for(; pos<=lim; pos+=ub(pos)) a[pos] = max(a[pos], val);
}
} aib1, aib2;
bool cmp(int a, int b)
{
return x[a] < x[b];
}
void solve(vector<int> &v)
{
if(v.empty()) return;
sort(v.begin(), v.end(), cmp);
for(auto pos : v)
come[pos] = max(aib1.query(x[pos]) - D * x[pos], aib2.query(lim - x[pos]) + U * x[pos]);
int sum = 0, best = -inf;
for(auto pos : v)
{
best = max(best, come[pos] + D * x[pos] - sum);
sum += p[pos];
dp[pos] = best + sum - D * x[pos];
}
sum = 0; best = -inf;
reverse(v.begin(), v.end());
for(auto pos : v)
{
best = max(best, come[pos] - U * x[pos] - sum);
sum += p[pos];
dp[pos] = max(dp[pos], best + sum + U * x[pos]);
}
for(auto pos : v)
{
aib1.update(x[pos], dp[pos] + D * x[pos]);
aib2.update(lim - x[pos], dp[pos] - U * x[pos]);
}
}
int main()
{
// freopen("input", "r", stdin);
int i, day, S, n;
cin >> n >> U >> D >> S;
for(i=1; i<=n; ++i)
{
cin >> day >> x[i] >> p[i];
event[day].push_back(i);
}
event[lim+1].push_back(n+1);
x[n+1] = S; p[n+1] = 0;
aib1.init(); aib2.init();
aib1.update(S, D * S);
aib2.update(lim - S, -U*S);
for(i=1; i<=lim+1; ++i) solve(event[i]);
cout << dp[n+1] << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |