JAG Contest 2016 Domestic B - 豪邸と宅配便

,

https://beta.atcoder.jp/contests/jag2016-domestic/tasks/jag2016secretspring_b

本番はちらっと見てDP感があったので他のメンバーに投げた。

後から解いてみたらDPは不要であった。 問題の理解に少し手間取った(時刻は$T+1$個あるがそれらに幅はない、$T$単位時間ある)。

solution

各時刻が使えるかどうかを愚直に調べていけばよい。$O(T)$。

$T \le 10000$と小さいので可能。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
using namespace std;
int main() {
    int n, m, t; cin >> n >> m >> t;
    vector<bool> used(t);
    int i = 0;
    while (n --) {
        int a; cin >> a;
        for (setmax(i, a-m); i < min(t, a+m); ++ i) used[i] = true;
    }
    cout << count(used.begin(), used.end(), false) << endl;
    return 0;
}