BOJ 23834 커여운 키위

문제 링크입니다.

풀이

기본적으로 전부 양의 방향으로 이동한다고 생각합니다. 그러면 M번 안에 한 번씩은 음의 방향으로 이동해야 할 때 음의 방향으로 이동해야 하는 최소 거리를 구해 두면 문제를 해결할 수 있습니다.

d[i] := i번째 움직임이 음의 방향일 때 조건을 만족하면서 음의 방향으로 이동해야 하는 최솟값으로 정의합니다. 그러면 최근 M개의 d 값을 단조성을 유지하도록 덱으로 관리해주면서 답을 갱신하는 것으로 $\mathcal{O}(N)$에 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll a[505050], asum[505050], b[505050], d[505050];
deque<pll> dq;

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		asum[i] = asum[i-1]+a[i];
	}
	for(int i = 1; i <= n; i++) cin >> b[i];
	dq.push_back({0, 0});
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		while(dq.size() && dq.front().second+m < i) dq.pop_front();
		if(i >= m) ans = max(ans, asum[i]-2*d[i-m]+b[i]);
		ans = max(ans, asum[i]-2*dq.front().first);
		d[i] = dq.front().first+a[i];
		while(dq.size() && dq.back().first >= d[i]) dq.pop_back();
		dq.push_back({d[i], i});
	}
	cout << ans;
}