# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
235499 | miello | Salesman (IOI09_salesman) | C++14 | 3089 ms | 12760 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
const int MXN = 5e5 + 5;
const int INF = 1e9 + 7;
vector<iii> fair;
int dp[MXN], n, u, d, s;
int dist(int start, int stop) {
int now, fi, sc;
if(start == -1) {
fi = s, sc = fair[stop].second.first;
} else if(stop == -1) {
fi = fair[start].second.first, sc = s;
} else {
fi = fair[start].second.first, sc = fair[stop].second.first;
}
if(fi < sc) {
now = u * (sc - fi);
} else {
now = d * (fi - sc);
}
return now;
}
int main() {
scanf("%d %d %d %d", &n, &u, &d, &s);
for(int i = 0; i < n; i++) {
int t, l, m;
scanf("%d %d %d", &t, &l, &m);
fair.emplace_back(t, ii(l, m));
}
if(u <= d) {
sort(fair.begin(), fair.end(), [](iii a, iii b) {
return a.first < b.first || (a.first == b.first && a.second.first < b.second.first);
});
} else {
sort(fair.begin(), fair.end(), [](iii a, iii b) {
return a.first < b.first || (a.first == b.first && a.second.first > b.second.first);
});
}
fill(dp + 1, dp + MXN, -INF);
for(int i = 1, stop = 0; i <= n; i++, stop++) {
int mx = -INF;
for(int j = 0, start = -1; j < i; j++, start++) {
mx = max(mx, dp[j] - dist(start, stop));
}
dp[i] = mx + fair[stop].second.second;
}
int p = 0;
for(int i = 1; i <= n; i++) {
p = max(p, dp[i] - dist(i - 1, -1));
}
printf("%d", p);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |