# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
139556 | 2019-08-01T03:00:59 Z | Boxworld | Salesman (IOI09_salesman) | C++14 | 1000 ms | 18992 KB |
#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++)ans[i]=-cost(a[0].dis,a[i].dis); 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4216 KB | Output is correct |
2 | Correct | 5 ms | 4216 KB | Output is correct |
3 | Correct | 6 ms | 4216 KB | Output is correct |
4 | Correct | 11 ms | 4344 KB | Output is correct |
5 | Correct | 62 ms | 4472 KB | Output is correct |
6 | Correct | 861 ms | 4984 KB | Output is correct |
7 | Execution timed out | 1070 ms | 5752 KB | Time limit exceeded |
8 | Execution timed out | 1072 ms | 7160 KB | Time limit exceeded |
9 | Execution timed out | 1091 ms | 8312 KB | Time limit exceeded |
10 | Execution timed out | 1076 ms | 12536 KB | Time limit exceeded |
11 | Execution timed out | 1059 ms | 13048 KB | Time limit exceeded |
12 | Execution timed out | 1061 ms | 15076 KB | Time limit exceeded |
13 | Execution timed out | 1065 ms | 15300 KB | Time limit exceeded |
14 | Execution timed out | 1080 ms | 18992 KB | Time limit exceeded |
15 | Execution timed out | 1069 ms | 18244 KB | Time limit exceeded |
16 | Execution timed out | 1079 ms | 18168 KB | Time limit exceeded |
17 | Incorrect | 6 ms | 4216 KB | Output isn't correct |
18 | Incorrect | 6 ms | 4216 KB | Output isn't correct |
19 | Incorrect | 8 ms | 4216 KB | Output isn't correct |
20 | Incorrect | 23 ms | 4472 KB | Output isn't correct |
21 | Incorrect | 20 ms | 4348 KB | Output isn't correct |
22 | Incorrect | 65 ms | 4344 KB | Output isn't correct |
23 | Incorrect | 63 ms | 4344 KB | Output isn't correct |
24 | Incorrect | 63 ms | 4404 KB | Output isn't correct |
25 | Execution timed out | 1067 ms | 6780 KB | Time limit exceeded |
26 | Execution timed out | 1073 ms | 9336 KB | Time limit exceeded |
27 | Execution timed out | 1067 ms | 12920 KB | Time limit exceeded |
28 | Execution timed out | 1063 ms | 13740 KB | Time limit exceeded |
29 | Execution timed out | 1072 ms | 16568 KB | Time limit exceeded |
30 | Execution timed out | 1070 ms | 17532 KB | Time limit exceeded |