【AtCoder】ABC 339 C - Perfect Bus | 茶コーダーが解くAtCoder

atcoder.jp

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

問題概要

一台のバスが走っており、乗客は常に非負整数である。このバスにはある時点において0人以上の乗客が乗っており、その時点から現在まで計 回停車した。 回目の停車では乗客が差引 人増加し、停車時以外では乗客の増減はなかった。ただし、 の場合もあり得る。与えられた情報に矛盾しない現在のバスの乗客の数として考えられる最小値を求めよ。

制約

• 入力はすべて整数。
• 
• 

考察

まずは最初に乗客が0人だったとしてシュミレーションしていく。途中で乗客数が負になったら、0にリセットしてシュミレーションを続ける。これを最後まで行ったときの乗客数が答えになる。

この人数より乗客数を減らすと、どこかで乗客数は負になり設定と矛盾する。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

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

int main()
{
    int N;
    cin >> N;
    ll ans = 0;
    rep(i, 0, N)
    {
        int A;
        cin >> A;

        ans += A;
        if (ans < 0)
            ans = 0;
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 10分