| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 69530 |
2018-08-21T08:08:35 Z |
gnoor |
Salesman (IOI09_salesman) |
C++17 |
|
1000 ms |
66560 KB |
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
long long treeu[2000100];
long long treed[2000100];
long long u,d;
void update(long long *seg,int idx,int l,int r,long long c,int k,long long val) {
if (l+1==r) {
seg[idx]=max(seg[idx],c*l+val);
return;
}
int m=(l+r)>>1;
if (k<m) update(seg,idx*2+1,l,m,c,k,val);
else update(seg,idx*2+2,m,r,c,k,val);
seg[idx]=max(seg[idx*2+1],seg[idx*2+2]);
}
long long query(long long *seg,int idx,int l,int r,int ll,int rr) {
if (rr<=l||ll>=r) return -1e18;
if (ll<=l&&rr>=r) return seg[idx];
int m=(l+r)>>1;
return max(query(seg,idx*2+1,l,m,ll,rr),query(seg,idx*2+2,m,r,ll,rr));
}
struct event {
int day,pos,cost;
};
bool operator< (const event &a, const event &b) {
return a.day<b.day;
}
event e[500100];
int main () {
int n,s;
scanf("%d%lld%lld%d",&n,&u,&d,&s);
for (int i=0;i<2000100;i++) {
treeu[i]=-1e18;
treed[i]=-1e18;
}
for (int i=0;i<n;i++) {
scanf("%d%d%d",&e[i].day,&e[i].pos,&e[i].cost);
}
sort(e,e+n);
update(treeu,0,1,500005,-u,s,0);
update(treed,0,1,500005,d,s,0);
long long cur;
for (int i=0;i<n;i++) {
cur=max(query(treeu,0,1,500005,e[i].pos+1,500005)+e[i].pos*u,query(treed,0,1,500005,1,e[i].pos)-e[i].pos*d);
cur+=e[i].cost;
update(treeu,0,1,500005,-u,e[i].pos,cur);
update(treed,0,1,500005,d,e[i].pos,cur);
}
long long ans=max(query(treeu,0,1,500005,s+1,500005)+s*u,query(treed,0,1,500005,1,s)-s*d);
printf("%lld\n",ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld%lld%d",&n,&u,&d,&s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&e[i].day,&e[i].pos,&e[i].cost);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
24 ms |
31720 KB |
Output is correct |
| 3 |
Correct |
24 ms |
31720 KB |
Output is correct |
| 4 |
Correct |
25 ms |
31720 KB |
Output is correct |
| 5 |
Correct |
30 ms |
31876 KB |
Output is correct |
| 6 |
Correct |
55 ms |
32520 KB |
Output is correct |
| 7 |
Correct |
114 ms |
33796 KB |
Output is correct |
| 8 |
Correct |
203 ms |
36212 KB |
Output is correct |
| 9 |
Correct |
319 ms |
39080 KB |
Output is correct |
| 10 |
Incorrect |
566 ms |
45668 KB |
Output isn't correct |
| 11 |
Correct |
619 ms |
50976 KB |
Output is correct |
| 12 |
Incorrect |
774 ms |
58220 KB |
Output isn't correct |
| 13 |
Correct |
794 ms |
64724 KB |
Output is correct |
| 14 |
Execution timed out |
1050 ms |
66560 KB |
Time limit exceeded |
| 15 |
Runtime error |
805 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 16 |
Runtime error |
941 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 17 |
Runtime error |
35 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 18 |
Runtime error |
24 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 19 |
Runtime error |
33 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 20 |
Runtime error |
28 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 21 |
Runtime error |
28 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 22 |
Runtime error |
30 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 23 |
Runtime error |
31 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 24 |
Runtime error |
39 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 25 |
Runtime error |
263 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 26 |
Runtime error |
357 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 27 |
Runtime error |
683 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 28 |
Runtime error |
740 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 29 |
Runtime error |
955 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 30 |
Runtime error |
967 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
