# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
138837 | Boxworld | Salesman (IOI09_salesman) | C++14 | 1086 ms | 19204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N=500100;
struct fair{int day,dis,val;}a[N];
int n,u,d,s;
long long ans[N];
bool cmp(fair x,fair y){return x.day<y.day;}
long long cost(int x1,int x2){
if (x1<x2)return (x2-x1)*u;
return (x1-x2)*d;
}
int main(){
scanf("%d%d%d%d",&n,&u,&d,&s);
a[0].dis=a[n+1].dis=s;
a[0].val=a[n+1].val=0;
for (int i=1;i<=n;i++)scanf("%d%d%d",&a[i].day,&a[i].dis,&a[i].val);
sort(a+1,a+n+1,cmp);
memset(ans,0,sizeof(ans));
ans[0]=0;
for (int i=1;i<=n+1;i++)
for (int j=0;j<i;j++)
ans[i]=max(ans[i],ans[j]-cost(a[j].dis,a[i].dis)+a[i].val);
printf("%lld\n",ans[n+1]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |