BZOJ 3203: [Sdoi2013]保护出题人

bzoj_3203.cpp

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef long double LD;
const int kN = 1e5+10;
int N;
LL D;
LL A[kN], X[kN], SUM[kN];
 
struct Queue{
    int a[kN], q_s, q_t;
    void Init(int n) {
        q_t = n;
        q_s = n+1;
    }
    int Size() {
        return q_t-q_s+1;
    }
    void PopFront() {
        q_s++;
    }
    void PushFront(int v) {
        a[--q_s] = v;
    }
    int & operator [] (int i) {
        return a[q_s+i];
    }
}Q;
 
void TestQueue() {
    Q.Init(10);
    Q[0] = 8;
    printf("%d\n", Q[0]);
}
 
LD Slope(int i, int j) {
    LD x = (i-j)*D;
    LD y = SUM[j]-SUM[i];
    return y/x;
}
 
LD CalcAns(int n, int i) {
    LD dis = X[n]+(n-i)*D;
    LD sum = SUM[i]-SUM[n+1];
    return sum/dis;
}
 
int main() {
    //TestQueue();
    //freopen("in.txt", "r", stdin);
    scanf("%d %lld", &N, &D);
    for (int i = 1; i <= N; i++) {
        scanf("%lld %lld", A+i, X+i);
    }
     
    for (int i = N; i >= 1; i--) {
        SUM[i] = SUM[i+1]+A[i];
    }
     
     
    LD ans = 0;
    Q.Init(N);
    for (int i = 1; i <= N; i++) {
        while (Q.Size() > 1 && Slope(i, Q[0]) <= Slope(Q[0], Q[1])) {
            Q.PopFront();
        }
        Q.PushFront(i);
         
        int l = 0, r = Q.Size()-1;
        while (r-l >= 3) {
            int d = (r-l)/3;
            int mid1 = l+d;
            int mid2 = l+d*2;
            LD v1 = CalcAns(i, Q[mid1]);
            LD v2 = CalcAns(i, Q[mid2]);
            if (v1 < v2) l = mid1;
            else r = mid2;
        }
        LD tmp = 0;
        for (int j = l; j <= r; j++) {
            tmp = max(tmp, CalcAns(i, Q[j]));
        }
        ans += tmp;
        //printf("solved : %d ans = %.10Lf\n", i, ans);
    }
     
    printf("%.0Lf\n", ans);
    //printf("%lld\n", LL(ans));
    return 0;
}