# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
596236 | mosiashvililuka | Salesman (IOI09_salesman) | C++14 | 803 ms | 59876 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const long long N=-999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,U,D,S,seglf[2000009],segrg[2000009],l,r,z,za,X[500009],pas,Y[500009],lf[500009],rg[500009];
vector <pair <long long, long long> > v[500009];
void UPD(int q, int w){
long long qw=w-q*D;
int rr=za+q-1;
segrg[rr]=qw;rr/=2;
while(rr!=0){
segrg[rr]=max(segrg[rr*2],segrg[rr*2+1]);
rr/=2;
}
qw=w+q*U;
rr=za+q-1;
seglf[rr]=qw;rr/=2;
while(rr!=0){
seglf[rr]=max(seglf[rr*2],seglf[rr*2+1]);
rr/=2;
}
}
void readlf(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,seglf[rr]);
return;
}
readlf(q,(q+w)/2,rr*2);
readlf((q+w)/2+1,w,rr*2+1);
}
void readrg(int q, int w, int rr){
if(q>r||w<l) return;
if(q>=l&&w<=r){
z=max(z,segrg[rr]);
return;
}
readrg(q,(q+w)/2,rr*2);
readrg((q+w)/2+1,w,rr*2+1);
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>U>>D>>S;swap(U,D);
for(i=1; i<=a; i++){
cin>>c>>d>>e;
v[c].push_back({d,e});
}
za=1;
while(za<500001) za*=2;
for(i=0; i<=za*2; i++){
seglf[i]=segrg[i]=N;
}
UPD(S,0);
for(ii=1; ii<=500001; ii++){
if(v[ii].size()==0) continue;
sort(v[ii].begin(),v[ii].end());
for(j=0; j<v[ii].size(); j++){
c=v[ii][j].first;d=v[ii][j].second;
l=1;r=c;z=N;
readlf(1,za,1);
z=z-c*U+d;
X[c]=z;
l=c;r=500001;z=N;
readrg(1,za,1);
z=z+c*D+d;
X[c]=max(X[c],z);
}
/*for(j=0; j<v[ii].size(); j++){
c=v[ii][j].first;d=v[ii][j].second;
UPD(c,X[c]);
}*/
zx=N;
for(j=0; j<v[ii].size(); j++){
c=v[ii][j].first;d=v[ii][j].second;
zx+=d;
zx=max(zx,X[c]+c*U);
Y[c]=zx-c*U;
}
zx=N;
for(j=v[ii].size()-1; j>=0; j--){
c=v[ii][j].first;d=v[ii][j].second;
zx+=d;
zx=max(zx,X[c]-c*D);
Y[c]=max(Y[c],zx+c*D);
}
zx=N;
for(j=0; j<v[ii].size(); j++){
c=v[ii][j].first;d=v[ii][j].second;
zx+=d;
zx=max(zx,X[c]+c*U*2LL);
lf[c]=zx-c*U;
}
zx=N;
for(j=v[ii].size()-1; j>=0; j--){
c=v[ii][j].first;d=v[ii][j].second;
zx+=d;
zx=max(zx,X[c]-c*D*2LL);
rg[c]=zx+c*D;
}
//
zx=N;
for(j=v[ii].size()-1; j>=0; j--){
c=v[ii][j].first;d=v[ii][j].second;
zx+=d;
Y[j]=max(Y[j],zx+c*D);
zx=max(zx,rg[c]);
}
zx=N;
for(j=0; j<v[ii].size(); j++){
c=v[ii][j].first;d=v[ii][j].second;
zx+=d;
Y[j]=max(Y[j],zx-c*U);
zx=max(zx,lf[c]);
}
//
for(j=0; j<v[ii].size(); j++){
c=v[ii][j].first;d=v[ii][j].second;
X[c]=max(X[c],Y[c]);
UPD(c,X[c]);
}
}
c=S;
l=1;r=c;z=N;
readlf(1,za,1);
z=z-c*U;
pas=max(pas,z);
l=c;r=500001;z=N;
readrg(1,za,1);
z=z+c*D;
pas=max(pas,z);
cout<<pas;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |