| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53496 |
2018-06-30T06:25:46 Z |
김세빈(#1419) |
Salesman (IOI09_salesman) |
C++11 |
|
3 ms |
620 KB |
#include <bits/stdc++.h>
using namespace std;
int T[505050], S[505050], C[505050], K[505050];
int dp[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]]);
}
for(i=l+1;i<r;i++){
dp[K[i]] = max(dp[K[i]], dp[K[i-1]] - d * (S[K[i]] - S[K[i-1]]));
}
for(i=r-2;i>=l;i--){
dp[K[i]] = max(dp[K[i]], dp[K[i+1]] - u * (S[K[i+1]] - S[K[i]]));
}
for(i=l;i<r;i++){
dp[K[i]] += C[K[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]]);
}
}
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:90:21: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
printf("%lld\n",ans);
^
salesman.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
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 |
248 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
356 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 10 |
Correct |
3 ms |
544 KB |
Output is correct |
| 11 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 12 |
Correct |
3 ms |
544 KB |
Output is correct |
| 13 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 14 |
Incorrect |
3 ms |
544 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
560 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 19 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 20 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 21 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 22 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 23 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 24 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 25 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 26 |
Incorrect |
2 ms |
616 KB |
Output isn't correct |
| 27 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 28 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 29 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 30 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
