CODE FESTIVAL 2016 Relay: H - 早起き / Early Bird

,

http://cf16-relay-open.contest.atcoder.jp/tasks/relay_h

overflowとちょうど$3,7$時の両方を含むことの見落しで$2$WA。

solution

$T = 0$として各時刻での起床回数を計算し、早起きとなる区間をスライドさせつつ$T$を$0$から$86399$まで動かし、その最大を出力すればよい。一日の秒数を$T$として$O(N + T)$。

implementation

#include <iostream>
#include <vector>
#include <numeric>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
const int l  = 60 * 60 * 24;
const int l3 = 60 * 60 * 3 + 1;
int main() {
    int n; cin >> n;
    vector<int> cnt(l);
    for (int t = 0; n --; ) {
        int a, b; cin >> a >> b;
        t += a;
        t %= l;
        cnt[t] += 1;
        t += b;
    }
    int ans = 0;
    int acc = accumulate(cnt.begin(), cnt.begin() + l3, 0);
    repeat (t,l) {
        acc += - cnt[t] + cnt[(t + l3) % l];
        setmax(ans, acc);
    }
    cout << ans << endl;
    return 0;
}