実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 19

問題概要

水の入っていない加湿器が1つあり、現在時刻は $0$ である。

この加湿器にこれから $N$ 回水を追加する。 $i$ 回目の水の追加は時刻 $T_i$ に行い、水を $V_i$ リットル追加する。ただし、加湿器には穴が空いていて、加湿器に水が入っている間は単位時間あたり水が $1$ リットル減り続ける。

時刻 $T_N$ に水を追加し終えたとき、加湿器に残っている水の量を求めよ。

制約

入力は全て整数。
$1 \leq N \leq 100$
$1 \leq T_i, V_i \leq 100$
$T_i \lt T_{i+1}$

考察

基本的には、 $T_i$ 時点での加湿器の水の量をシミュレーションしていけばよい。

直前に水を入れた時刻を $\mathrm{last}$ とすれば、新たに水を追加するタイミングで事前に $T_i - \mathrm{last}$ を引けば、穴から出ていく水の量をシミュレートできる。

また、水の量が負になったら $0$ に戻すことを忘れないようにすること。

コード

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> T(N), V(N);
    rep(i, 0, N) cin >> T[i] >> V[i];

    int water = 0;
    int last = 0;
    rep(i, 0, N)
    {
        water -= (T[i] - last);

        chmax(water, 0);

        water += V[i];
        last = T[i];
    }

    cout << water << endl;
}