| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53505 |
2018-06-30T06:39:43 Z |
김세빈(#1419) |
Salesman (IOI09_salesman) |
C++11 |
|
1000 ms |
32576 KB |
#include <bits/stdc++.h>
using namespace std;
int T[505050], S[505050], C[505050], K[505050];
int dp[505050], L[505050], R[505050];
int U[1101010], D[1101010];
int n,u,d,s,ans,sz;
bool comp_T(int ca, int cb) { return T[ca] < T[cb]; }
bool comp_S(int ca, int cb) { return S[ca] < S[cb]; }
void update(int* A, int p, int v)
{
p += sz;
A[p] = max(A[p], v);
for(p>>=1;p;p>>=1){
A[p] = max(A[p<<1], A[p<<1|1]);
}
}
int find_max(int* A, int l, int r)
{
int ret = -1e9;
l += sz, r += sz;
for(;l<r;){
if(l & 1) ret = max(ret, A[l]);
if(~r & 1) ret = max(ret, A[r]);
l = l+1 >> 1;
r = r-1 >> 1;
}
if(l == r) ret = max(ret, A[l]);
return ret;
}
int main()
{
//freopen("input.txt","r",stdin);
int i,l,r;
scanf("%d%d%d%d",&n,&u,&d,&s);
for(sz=1;sz <= s;) sz <<= 1;
for(i=0;i<n;i++){
scanf("%d%d%d",T+i,S+i,C+i);
K[i] = i;
for(;sz <= S[i];) sz <<= 1;
}
for(i=1;i<sz+sz;i++) U[i] = D[i] = -1e9;
sort(K, K+n, comp_T);
update(D, s, d * s);
update(U, s, -u * s);
for(l=0;l<n;l=r){
for(r=l;r<n && T[K[r]]==T[K[l]];r++);
sort(K+l, K+r, comp_S);
for(i=l;i<r;i++){
dp[K[i]] = max(find_max(D, 0, S[K[i]]) - d * S[K[i]], find_max(U, S[K[i]], sz-1) + u * S[K[i]]) + C[K[i]];
}
L[l] = dp[K[l]];
for(i=l+1;i<r;i++){
L[i] = max(dp[K[i]], L[i-1] - d * (S[K[i]] - S[K[i-1]]) + C[K[i]]);
}
R[r] = dp[K[r]];
for(i=r-2;i>=l;i--){
R[r] = max(dp[K[i]], R[i+1] - u * (S[K[i+1]] - S[K[i]]) + C[K[i]]);
}
for(i=l;i<r;i++){
dp[K[i]] = max(dp[K[i]], max(L[i], R[i]));
update(D, S[K[i]], dp[K[i]] + d * S[K[i]]);
update(U, S[K[i]], dp[K[i]] - u * S[K[i]]);
printf("%d %d %d\n",S[K[i]],C[K[i]],dp[K[i]]);
}
}
for(i=0;i<n;i++){
if(S[i] > s) ans = max(ans, dp[i] - u * (S[i] - s));
else ans = max(ans, dp[i] - d * (s - S[i]));
}
printf("%lld\n",ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int find_max(int*, int, int)':
salesman.cpp:31:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
l = l+1 >> 1;
~^~
salesman.cpp:32:8: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
r = r-1 >> 1;
~^~
salesman.cpp: In function 'int main()':
salesman.cpp:93:21: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
printf("%lld\n",ans);
^
salesman.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d",&n,&u,&d,&s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",T+i,S+i,C+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
536 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
828 KB |
Output isn't correct |
| 5 |
Incorrect |
7 ms |
828 KB |
Output isn't correct |
| 6 |
Incorrect |
41 ms |
9636 KB |
Output isn't correct |
| 7 |
Incorrect |
89 ms |
11048 KB |
Output isn't correct |
| 8 |
Incorrect |
199 ms |
13496 KB |
Output isn't correct |
| 9 |
Incorrect |
279 ms |
15272 KB |
Output isn't correct |
| 10 |
Incorrect |
535 ms |
20672 KB |
Output isn't correct |
| 11 |
Incorrect |
570 ms |
22644 KB |
Output isn't correct |
| 12 |
Incorrect |
828 ms |
24104 KB |
Output isn't correct |
| 13 |
Incorrect |
820 ms |
26512 KB |
Output isn't correct |
| 14 |
Execution timed out |
1024 ms |
32576 KB |
Time limit exceeded |
| 15 |
Incorrect |
891 ms |
32576 KB |
Output isn't correct |
| 16 |
Execution timed out |
1075 ms |
32576 KB |
Time limit exceeded |
| 17 |
Incorrect |
3 ms |
32576 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
32576 KB |
Output isn't correct |
| 19 |
Incorrect |
3 ms |
32576 KB |
Output isn't correct |
| 20 |
Incorrect |
9 ms |
32576 KB |
Output isn't correct |
| 21 |
Incorrect |
6 ms |
32576 KB |
Output isn't correct |
| 22 |
Incorrect |
7 ms |
32576 KB |
Output isn't correct |
| 23 |
Incorrect |
7 ms |
32576 KB |
Output isn't correct |
| 24 |
Incorrect |
9 ms |
32576 KB |
Output isn't correct |
| 25 |
Incorrect |
214 ms |
32576 KB |
Output isn't correct |
| 26 |
Incorrect |
465 ms |
32576 KB |
Output isn't correct |
| 27 |
Incorrect |
710 ms |
32576 KB |
Output isn't correct |
| 28 |
Incorrect |
614 ms |
32576 KB |
Output isn't correct |
| 29 |
Incorrect |
900 ms |
32576 KB |
Output isn't correct |
| 30 |
Incorrect |
897 ms |
32576 KB |
Output isn't correct |
