# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53511 |
2018-06-30T06:45:04 Z |
노영훈(#1418) |
Salesman (IOI09_salesman) |
C++11 |
|
1000 ms |
24200 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=1e9, XMX=5000001;
int n, d, u, s;
struct shop {
int t, x, a;
} S[MX];
struct Seg {
int tree[MX*4], n;
void init(int sz){
n=sz;
for(int i=1; i<4*n; i++) tree[i]=-inf;
}
void upt(int v, int s, int e, int pos, int val){
if(pos<s || e<pos) return;
if(s==e){
tree[v]=val;
return;
}
upt(v*2,s,(s+e)/2,pos,val);
upt(v*2+1,(s+e)/2+1,e,pos,val);
tree[v]=max(tree[v*2], tree[v*2+1]);
}
void upt(int pos, int val){
upt(1,1,n,pos,val);
}
int mx(int v, int s, int e, int l, int r){
if(r<s || e<l) return -inf;
if(l<=s && e<=r) return tree[v];
return max(mx(v*2,s,(s+e)/2,l,r), mx(v*2+1,(s+e)/2+1,e,l,r));
}
int mx(int l, int r){
if(r<l) return -inf;
return mx(1,1,n,l,r);
}
} US, DS;
int D[MX];
void upt(int pos, int val){
D[pos]=val;
US.upt(pos, val-u*(XMX-pos));
DS.upt(pos, val-d*(pos));
}
int get(int x){
int upmx=US.mx(1,x), dnmx=DS.mx(x,XMX);
upmx+=u*(XMX-x);
dnmx+=d*(x);
return max(upmx, dnmx);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>u>>d>>s;
for(int i=1; i<=n; i++){
int t,x,a;
cin>>t>>x>>a;
S[i]={t,x,a};
}
sort(S+1, S+n+1, [](shop &a, shop &b){
return a.t<b.t;
});
DS.init(500001);
US.init(500001);
for(int i=1; i<=n; i++)
upt(i,-inf);
upt(s, 0);
for(int i=1; i<=n; i++){
int now=get(S[i].x);
upt(S[i].x, now+S[i].a);
}
cout<<get(s);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
15996 KB |
Output is correct |
2 |
Correct |
15 ms |
15996 KB |
Output is correct |
3 |
Correct |
18 ms |
16284 KB |
Output is correct |
4 |
Correct |
19 ms |
16284 KB |
Output is correct |
5 |
Correct |
21 ms |
16384 KB |
Output is correct |
6 |
Correct |
54 ms |
18432 KB |
Output is correct |
7 |
Correct |
119 ms |
18756 KB |
Output is correct |
8 |
Correct |
254 ms |
19488 KB |
Output is correct |
9 |
Correct |
307 ms |
19900 KB |
Output is correct |
10 |
Correct |
638 ms |
21868 KB |
Output is correct |
11 |
Correct |
679 ms |
21868 KB |
Output is correct |
12 |
Correct |
965 ms |
22988 KB |
Output is correct |
13 |
Correct |
804 ms |
23012 KB |
Output is correct |
14 |
Correct |
948 ms |
24028 KB |
Output is correct |
15 |
Correct |
783 ms |
24164 KB |
Output is correct |
16 |
Execution timed out |
1093 ms |
24200 KB |
Time limit exceeded |
17 |
Incorrect |
14 ms |
24200 KB |
Output isn't correct |
18 |
Incorrect |
14 ms |
24200 KB |
Output isn't correct |
19 |
Incorrect |
16 ms |
24200 KB |
Output isn't correct |
20 |
Incorrect |
17 ms |
24200 KB |
Output isn't correct |
21 |
Incorrect |
17 ms |
24200 KB |
Output isn't correct |
22 |
Incorrect |
19 ms |
24200 KB |
Output isn't correct |
23 |
Incorrect |
21 ms |
24200 KB |
Output isn't correct |
24 |
Incorrect |
20 ms |
24200 KB |
Output isn't correct |
25 |
Incorrect |
192 ms |
24200 KB |
Output isn't correct |
26 |
Incorrect |
367 ms |
24200 KB |
Output isn't correct |
27 |
Incorrect |
663 ms |
24200 KB |
Output isn't correct |
28 |
Incorrect |
659 ms |
24200 KB |
Output isn't correct |
29 |
Execution timed out |
1028 ms |
24200 KB |
Time limit exceeded |
30 |
Execution timed out |
1008 ms |
24200 KB |
Time limit exceeded |