백준11001 김치

작성일 | In

문제 링크

  • http://icpc.me/11001

사용 알고리즘

  • DnC Optimization

시간복잡도

  • O(NlogN)

풀이

C(i, j) = (j - i) * Tj + Vi로 정의합시다.

a ≤ b ≤ c ≤ d인 a, b, c, d에 대해 c(a, d) + c(b, c) ≤ c(a, c) + c(b, d)가 성립하므로 DnC Optimization을 사용할 수 있습니다. DnC Opt 설명

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<ll> t, v;
int n, d;

ll ans;

inline ll c(ll i, ll j){
	return (j - i) * t[j] + v[i];
}

void f(int s, int e, int l, int r){
	if(s > e) return;
	int m = s + e >> 1;
	int k = max(l, m - d);
	for(int i=k; i≤min(m, r); i++){
		if(c(k, m) < c(i, m)) k = i;
	}
	ans = max(ans, c(k, m));
	f(s, m-1, l, k);
	f(m+1, e, k, r);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> d; v.resize(n+1); t.resize(n+1);

	for(int i=1; i<=n; i++) cin >> t[i];
	for(int i=1; i<=n; i++) cin >> v[i];
	f(1, n, 1, n);

	cout << ans;
}