All Japan Association of Return home [ACPC2017 Day1 B]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day1&pid=B

解説

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2536812&cid=ACPC2017Day1

戻る余裕があるなら戻る。
余裕が無いなら直接行くを繰り返す貪欲。

typedef long long ll;
int N, D, T[101010], F[101010];
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, N) cin >> T[i] >> F[i];
 
    ll ans = 0;
    int t = 0, f = 1, h = 0;
    rep(i, 0, N) {
        int d = abs(f - F[i]);
        int dd = f - 1 + F[i] - 1;
 
        if (t + dd <= T[i]) {
            ans += 1LL * (f - 1) * h;
            t = T[i];
            f = F[i];
            h = 1;
            continue;
        }
 
        if (t + d <= T[i]) {
            ans += 1LL * (T[i] - t) * h;
            t = T[i];
            f = F[i];
            h++;
            if (D < h) {
                printf("-1\n");
                return;
            }
            continue;
        }
 
        printf("-1\n");
        return;
    }
    ans += 1LL * (f - 1) * h;
    cout << ans << endl;
}