| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1105015 | salmon | Salesman (IOI09_salesman) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int N;
int D,U;
int S;
vector<pair<int,int>> f[500100];
int best[500100];
map<int,int> sat;
const int inf = 2.1e9;
int retrieve(int p){
int num = -inf;
if(sat.find(p) != sat.end()){
auto it = sat.find(p);
num = it -> second;
}
else{
auto it = sat.lower_bound(p);
if(it != sat.end()){
num = max(num, it -> second - U * (it -> first - p) );
}
if(it != sat.begin()){
advance(it,-1);
num = max(num, it -> second - D * (p - it -> first) );
}
}
return num;
}
int main(){
scanf(" %d",&N);
scanf(" %d",&U);
scanf(" %d",&D);
scanf(" %d",&S);
for(int i = 0; i < N; i++){
int T,L,M;
scanf(" %d",&T);
scanf(" %d",&L);
scanf(" %d",&M);
f[T].push_back({L,M});
}
sat.insert({S,0});
for(int i = 1; i < 500100; i++){
sort(f[i].begin(),f[i].end());
if(f[i].empty()) continue;
int past = -inf;
for(int j = 0; j < f[i].size(); j++){
int num = retrieve(f[i][j].first) + f[i][j].first * D;
if(j == 0) best[j] = num + f[i][j].second;
else{
best[j] = max(best[j - 1], num) + f[i][j].second;
}
}
for(int j = 0; j < f[i].size(); j++){
best[j] -= f[i][j].first * D;
}
for(int j = f[i].size() - 1; j >= 0; j--){
past = max(past, retrieve(f[i][j].first) - f[i][j].first * U) + f[i][j].second;
best[j] = max(best[j], past + f[i][j].first * U);
}
for(int j = 0; j < f[i].size(); j++){
pair<int,int> ii = f[i][j];
int num = best[j];
sat.erase(ii.first);
if(retrieve(ii.first) >= ii.second){
continue;
}
while(true){
auto it = sat.lower_bound(ii.first);
if(it == sat.end()) break;
if(it -> second <= num - (it -> first - ii.first) * D ){
sat.erase(it);
}
else if(){
}
else break;
}
while(true){
auto it = sat.lower_bound(ii.first);
if(it == sat.begin()) break;
advance(it,-1);
if(it -> second <= num - (ii.first - it -> first) * U ){
sat.erase(it);
}
else break;
}
sat.insert({ii.first, num});
}
}
auto it = sat.lower_bound(S);
int ans = -inf;
if(it != sat.end()){
ans = max(ans, it -> second - U * (it -> first - S) );
}
if(it != sat.begin()){
advance(it,-1);
ans = max(ans, it -> second - D * (S - it -> first));
}
printf("%d",ans);
}