oj.uz

Submission #53488

# Submission time Handle Problem Language Result Execution time Memory
53488 2018-06-30T06:12:02 Z 김세빈(#1419) Salesman (IOI09_salesman) C++11
58 / 100
 867 ms 37688 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_K(int ca, int cb) { return K[ca] < K[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()
{	
	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;T[K[r]]==T[K[l]];r++);
		sort(K+l, K+r, comp_K);
		
		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-1;i>=r;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:88:21: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  printf("%lld\n",ans);
                     ^
salesman.cpp:43: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:48: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
58.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 2296 KB Output isn't correct
2 Correct 2 ms 2296 KB Output is correct
3 Correct 4 ms 2296 KB Output is correct
4 Correct 4 ms 2296 KB Output is correct
5 Correct 6 ms 2296 KB Output is correct
6 Correct 33 ms 9648 KB Output is correct
7 Correct 76 ms 11244 KB Output is correct
8 Correct 162 ms 13832 KB Output is correct
9 Correct 220 ms 17112 KB Output is correct
10 Correct 448 ms 24992 KB Output is correct
11 Correct 428 ms 30372 KB Output is correct
12 Correct 602 ms 35540 KB Output is correct
13 Correct 569 ms 35552 KB Output is correct
14 Correct 744 ms 37688 KB Output is correct
15 Correct 687 ms 37688 KB Output is correct
16 Correct 712 ms 37688 KB Output is correct
17 Incorrect 139 ms 37688 KB Output isn't correct
18 Incorrect 3 ms 37688 KB Output isn't correct
19 Incorrect 3 ms 37688 KB Output isn't correct
20 Incorrect 4 ms 37688 KB Output isn't correct
21 Incorrect 5 ms 37688 KB Output isn't correct
22 Incorrect 7 ms 37688 KB Output isn't correct
23 Incorrect 6 ms 37688 KB Output isn't correct
24 Incorrect 6 ms 37688 KB Output isn't correct
25 Incorrect 132 ms 37688 KB Output isn't correct
26 Incorrect 262 ms 37688 KB Output isn't correct
27 Incorrect 587 ms 37688 KB Output isn't correct
28 Incorrect 560 ms 37688 KB Output isn't correct
29 Incorrect 780 ms 37688 KB Output isn't correct
30 Incorrect 867 ms 37688 KB Output isn't correct