oj.uz

답안 #53493

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53493 2018-06-30T06:22:28 Z 김세빈(#1419) Salesman (IOI09_salesman) C++11
3 / 100
 741 ms 18784 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()
{	
	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-1;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: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
3.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Incorrect 2 ms 548 KB Output isn't correct
3 Incorrect 2 ms 548 KB Output isn't correct
4 Incorrect 4 ms 588 KB Output isn't correct
5 Correct 6 ms 844 KB Output is correct
6 Incorrect 30 ms 9048 KB Output isn't correct
7 Incorrect 91 ms 9692 KB Output isn't correct
8 Incorrect 139 ms 10760 KB Output isn't correct
9 Incorrect 214 ms 11656 KB Output isn't correct
10 Incorrect 389 ms 14688 KB Output isn't correct
11 Incorrect 406 ms 14728 KB Output isn't correct
12 Incorrect 528 ms 16744 KB Output isn't correct
13 Incorrect 588 ms 16744 KB Output isn't correct
14 Incorrect 740 ms 18680 KB Output isn't correct
15 Incorrect 741 ms 18724 KB Output isn't correct
16 Incorrect 717 ms 18724 KB Output isn't correct
17 Incorrect 3 ms 18724 KB Output isn't correct
18 Incorrect 4 ms 18724 KB Output isn't correct
19 Incorrect 3 ms 18724 KB Output isn't correct
20 Incorrect 5 ms 18724 KB Output isn't correct
21 Incorrect 4 ms 18724 KB Output isn't correct
22 Incorrect 5 ms 18724 KB Output isn't correct
23 Incorrect 6 ms 18724 KB Output isn't correct
24 Incorrect 6 ms 18724 KB Output isn't correct
25 Incorrect 164 ms 18724 KB Output isn't correct
26 Incorrect 244 ms 18724 KB Output isn't correct
27 Incorrect 436 ms 18724 KB Output isn't correct
28 Incorrect 475 ms 18724 KB Output isn't correct
29 Incorrect 693 ms 18784 KB Output isn't correct
30 Incorrect 687 ms 18784 KB Output isn't correct