Sequence [ACPC2017 Day2 H]

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

解法(途中)

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

下は汚いデバッグ用コードなど全部入り。
また書き直します。

数列が丸々入る部分を全探索する。
はみ出す左右の部分は三分探索で最大となるはみ出し方を見つける。

template<typename Func>
int findMax(int L, int R, Func f) { //[L, R)
    int lo = L, hi = R;
    while (lo + 1 != hi) {
        int mi = (lo + hi) / 2;
        if (f(mi) - f(mi - 1) > 0) lo = mi;
        else hi = mi;
    }
    return lo;
}
int getrand(int l, int r) { // [l, r]
    static uint32_t y = time(NULL);
    y ^= (y << 13); y ^= (y >> 17);
    y ^= (y << 5);
    return y % (r - l + 1) + l;
}
/*------------------------





typedef long long ll;
ll N, L, A[101010], D[101010];
ll K;
ll sm[101010];
ll smr[101010];
//--------------------------------------------------------------------------------------------------
ll get(int idx, ll X, ll Y) { // ??°???idx???[X,Y]
    if (X > Y) return 0;
    if (L < Y) Y = L;
    ll a = A[idx] + (X - 1) * D[idx];
    ll b = A[idx] + (Y - 1) * D[idx];
    return (Y - X + 1) * (a + b) / 2;
}
ll getback(int idx, ll X, ll Y) { // ??°???idx???????????????[X,Y]
    if (X > Y) return 0;
    if (L < Y) Y = L;
 
    ll AA = A[idx] + (L - 1) * D[idx];
    ll DD = -D[idx];
 
    ll a = AA + (X - 1) * DD;
    ll b = AA + (Y - 1) * DD;
    return (Y - X + 1) * (a + b) / 2;
}
//--------------------------------------------------------------------------------------------------
ll XX, YY, res;
ll f(int lef) {
    ll le = getback(XX - 1, 1, lef);
    ll ri = get(YY + 1, 1, res - lef);
    if (L < res - lef) return -(res - lef);
    if (res - lef < 1) return -(res - lef);
    return le + ri;
}
//--------------------------------------------------------------------------------------------------
ll naive() {
    vector<ll> v;
    rep(i, 0, N) rep(j, 0, L) v.push_back(A[i] + D[i] * j);
    //fore(i, v) printf("%lld\n", i);
 
    ll ans = 0;
    rep(i, 0, N * L) {
        int X = i;
        int Y = i + K - 1;
        if (N * L <= Y) break;
 
        ll sm = 0;
        rep(j, X, Y + 1) sm += v[j];
        ans = max(ans, sm);
    }
 
    return ans;
}
//--------------------------------------------------------------------------------------------------
void debug() {
    N = getrand(1, 5), L = getrand(1, 5), K = getrand(1, N * L);
    rep(i, 0, N) {
        A[i] = getrand(0, 10);
        D[i] = getrand(1, 10);
    }
}
//--------------------------------------------------------------------------------------------------
ll opt() {
    rep(i, 0, N) sm[i] = get(i, 1, L);
    smr[0] = sm[0];
    rep(i, 1, N) smr[i] = smr[i - 1] + sm[i];
 
    if (K == N * L) return smr[N - 1];
 
    if (K <= L) {
        ll ans = 0;
        rep(i, 0, N) ans = max(ans, getback(i, 1, K));
        rep(i, 0, N - 1) {
            XX = i + 1;
            YY = i;
            res = K;
            int lef = findMax(0, L, f);
            ans = max(ans, f(lef));
        }
        return ans;
    }
 
    ll cnt = K / L;
    ll ans = 0;
    rep(i, 0, N - cnt + 1) {
        int X = i;
        int Y = i + cnt - 1;
 
        ll XYsm = smr[Y];
        if (X) XYsm -= smr[X - 1];
 
        if (X == 0) ans = max(ans, XYsm + get(Y + 1, 1, K - cnt * L));
        else if (Y == N - 1) {
            ans = max(ans, XYsm + getback(X - 1, 1, K - cnt * L));
        }
        else {
            XX = X;
            YY = Y;
            res = K - cnt * L;
            int lef = findMax(0, res + 1, f);
            ans = max(ans, XYsm + f(lef));
        }
    }
 
    cnt--;
    rep(i, 0, N - cnt + 1) {
        int X = i;
        int Y = i + cnt - 1;
 
        ll XYsm = smr[Y];
        if (X) XYsm -= smr[X - 1];
 
        if (X == 0) {
            if(K - cnt * L <= L) ans = max(ans, XYsm + get(Y + 1, 1, K - cnt * L));
        }
        else if (Y == N - 1) {
            if(K - cnt * L <= L) ans = max(ans, XYsm + getback(X - 1, 1, K - cnt * L));
        }
        else {
            XX = X;
            YY = Y;
            res = K - cnt * L;
            int lef = findMax(0, L, f);
            ans = max(ans, XYsm + f(lef));
        }
    }
 
    return ans;
}
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> L >> K;
    rep(i, 0, N) cin >> A[i] >> D[i];
 
    //ll naive_ans = naive();
    //printf("%lld\n", naive_ans);
 
    ll ans = opt();
    printf("%lld\n", ans);
    return;
 
    rep(_, 0, 110) {
        debug();
 
        ll naive_ans = naive();
        //printf("%lld\n", naive_ans);
 
        ll ans = opt();
 
        //printf("%lld\n", ans);
 
        if (naive_ans != ans) {
            printf("!!\n");
            printf("%lld %lld %lld\n", N, L, K);
            rep(i, 0, N) printf("%lld %lld\n", A[i], D[i]);
            return;
        }
    }
}