# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133849 | figter001 | Salesman (IOI09_salesman) | C++17 | 1032 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 5e5 + 100;
vector<pair<int,int>> e[nax];
ll n,U,D,s,len;
ll up[4*nax],dn[4*nax];
ll dp[nax];
void init(){
for(int i=1;i<=len;i++)dp[i] = -1e10;
dp[s] = 0;
}
void build(int n,int s,int e){
if(s == e){
up[n] = dp[s] + s * U;
dn[n] = dp[s] - s * D;
return;
}
build(n*2,s,(s+e)/2);
build(n*2+1,(s+e)/2+1,e);
up[n] = max(up[n*2] , up[n*2+1]);
dn[n] = max(dn[n*2] , dn[n*2+1]);
}
void update(int n,int s,int e,int at){
if(s > at || e < at)return;
if(s == e){
up[n] = dp[s] - s * U;
dn[n] = dp[s] + s * D;
return;
}
update(n*2,s,(s+e)/2,at);
update(n*2+1,(s+e)/2+1,e,at);
up[n] = max(up[n*2] , up[n*2+1]);
dn[n] = max(dn[n*2] , dn[n*2+1]);
}
ll get(int n,int s,int e,int l,int r,int t){
if(s > r || e < l)return -1e18;
if(s >= l && e <= r){
if(t == 0)return up[n];
else if(t == 1)return dn[n];
}
return max( get(n*2,s,(s+e)/2,l,r,t) , get(n*2+1,(s+e)/2+1,e,l,r,t) );
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout << fixed;
cin>>n>>U>>D>>s;
len = s;
e[0].push_back({s,0});
int mxd=0;
for(int i=0;i<n;i++){
int d,l,m;
cin>>d>>l>>m;
e[d].push_back({l,m});
len = max(len,1ll*l);
mxd = max(mxd,d);
}
mxd++;
len++;
e[mxd].push_back({s,0});
init();
build(1,1,len);
for(int day=0;day<=mxd;day++){
if(e[day].empty())continue;
assert(e[day].size() == 1);
if(e[day].size() == 1){
int l = e[day][0].first;
int m = e[day][0].second;
ll cur = -1e18;
if(day != 0){
cur = max(cur, get(1,1,len,1,l,1) + m - D*l);
cur = max(cur, get(1,1,len,l,len,0) + m + U*l);
}
dp[l] = max(dp[l],cur);
update(1,1,len,l);
}else{
}
}
cout << dp[s] << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |