Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BZOJ 3203: [Sdoi2013]保护出题人
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.