Codeforces Round #219 (Div. 2) E. Watching Fireworks is Fun

문제 링크

n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).

수직선에 1, 2, ..., n 의 장소가 있다. m 개의 폭죽이 임의의 시간과 장소에서 발사된다.

주인공은 1초에 d만큼 이동할 수 있다. 시작 위치는 아무데서나 시작해도 된다.

i번 폭죽이 발사될 때 주인공이 x 지점에 있을 때 얻게되는 행복은 \(b_i - |a_i - x|\) 이다.

이 때 모든 폭죽이 발사되고 난 후에 주인공이 얻은 행복의 양이 최대가 되도록 하고싶다.

그 아랫줄부터는 m개의 폭죽의 대한 정보 ai, bi, ti 가 주어진다.

ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109)

dp[i][j] : t_i 시간에 j 위치에 있을 때 최대 행복도

\(dp[i][j] = b_i - |a_i - j| + max(dp[i - 1][k])(j - D \times (t_i - t_{i-1}) \le k \le j + D \times (t_i - t_{i-1})\)

그럼 구간의 최대값을 빠르게 계산해야하는데 만약 인덱스트리를 쓴다면 시간 복잡도는 \(O(NMlgN)\). 

하지만 이걸로는 너무 느리다. 그럼 \(O(NM)\) 으로 어떻게 줄일까? 선형시간으로 

일정한 L개의 연속된 구간의 최대(or 최소) 를 유지해주는 방법은 여기를 참고. 결론은 덱을 사용하면된다.

\(D \times (t_i - t_{i-1})\) 를 L 이라고할 때 이전 폭죽이 터지고나서 다음 폭죽때 까지

j의 좌우로 L위치에서 j로 이동할 수 있으므로 2 * L + 1 개의 연속된 최대를 유지하면 된다. 나머지는 잘 구현하면됨.

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
ll N, M, D;
ll dp[2][300003];
struct fire{
    ll a, b, t;
};
fire fires[303];
int main() {
    fastio();
    cin >> N >> M >> D;
    for (int i = 1; i <= M; i++){
        ll a, b, t;
        cin >> a >> b >> t;
        fires[i] = fire{ a, b, t };
    }
 
    for (int i = 1; i <= M; i++){
        ll L = min(2 * N, 2 * D * (fires[i].t - fires[i - 1].t) + 1);
        deque<int> dq;
        for (int j = N + 1; j <= 2 * N; j++) dp[(i + 1) % 2][j] = -infl;
        for (int j = 1; j <= 2 * N; j++){
            while (!dq.empty() && dq.front() <= j - L) dq.pop_front();
            while (!dq.empty() && dp[(i + 1) % 2][dq.back()] <= dp[(i + 1) % 2][j]) dq.pop_back();
            dq.push_back(j);
            ll mn = dp[(i + 1) % 2][dq.front()] + fires[i].b - abs(fires[i].a - (j - L / 2));
            if (0 < j - L / 2 && j - L / 2 <= N) dp[i % 2][j - L / 2] = mn;
        }
    }
 
    ll ans = -infl;
    for (int i = 1; i <= N; i++) ans = max(ans, dp[M % 2][i]);
    cout << ans;
 
    return 0;
}