| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 133789 | figter001 | Salesman (IOI09_salesman) | C++17 | 4 ms | 504 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;
int d[nax],l[nax],m[nax];
int n,U,D,s,len;
ll up[4*nax],dn[4*nax];
ll dp[nax];
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;
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif
cin>>n>>U>>D>>s;
n+=2;
d[0] = -1;l[0] = s;
d[n-1] = nax + 1;l[n-1] = s;
len = s;
for(int i=1;i<n;i++){
cin>>d[i]>>l[i]>>m[i];
len = max(len,l[i]);
}
len++;
vector<int> idx;
for(int i=0;i<n;i++)idx.push_back(i);
sort(idx.begin(),idx.end(), [&] (int a,int b) {
return d[a] < d[b];
});
for(int i=1;i<=len;i++)dp[i] = -1e10;
dp[s] = 0;
build(1,1,len);
int lst = -1;
for(int j=0;j<idx.size();j++){
int i = idx[j];
if(j == idx.size() - 1 || d[idx[j]] != d[idx[j+1]]){
ll cur = -1e18;
if(i != 0){
cur = max(cur, get(1,1,len,1,l[i],1) + m[i] - D*l[i]);
cur = max(cur, get(1,1,len,l[i],len,0) + m[i] + U*l[i]);
}
dp[l[i]] = max(dp[l[i]],cur);
update(1,1,len,l[i]);
}else{
vector<int> e;
while(j < idx.size() - 1 && d[idx[j]] == d[idx[j+1]]){
e.push_back(idx[j++]);
}
e.push_back(idx[j]);
sort(e.begin(),e.end(), [&] (int a,int b) {
return l[a] < l[b];
});
for(int x = 0;x<e.size();x++){
ll sum = 0;
int a = e[x];
for(int y=x;y<e.size();y++){
int b = e[y];
sum += m[b];
dp[l[a]] = max(dp[l[a]] , get(1,1,len,l[b],len,0) + sum + U*l[a]);
}
}
for(int x = 0;x<e.size();x++){
ll sum = 0;
int a = e[x];
for(int y=x;y>=0;y--){
int b = e[y];
sum += m[b];
dp[l[a]] = max(dp[l[a]] , get(1,1,len,1,l[b],1) + sum - D*l[a]);
}
}
for(int a : e){
update(1,1,len,l[a]);
}
}
}
cout << dp[s] << endl;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||