0_0_36700381_19491.cpp:2:2331: fatal error: GCC4.9.2/x86_64-w64-mingw32/include/c++/bits/stdc++.h>usin: Invalid argument
#include <bits/stdc++.h>using namespace std;typedef long long LL;template<typename T>inline void read(T &num) { char ch; int flg=1; while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg; for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar()); num*=flg;}const int MAXN = 100005;const double eps = 1e-10;struct Vector { LL x, y; Vector(){} Vector(LL _x, LL _y):x(_x), y(_y){} inline Vector operator -(const Vector &o) { return Vector(x-o.x, y-o.y); } inline double operator *(const Vector &o) { return (double)x*o.y - (double)y*o.x; } //longlong,double}p[MAXN], Q[MAXN];LL f[MAXN];struct Node { LL p, r, d, g, x, y; int id; inline void init() { read(d), read(p), read(r), read(g); x = g, y = -p+r-d*g-g; }}a[MAXN], tmp[MAXN];inline bool cmpD(const Node &A, const Node &B) { return A.d < B.d; }inline bool cmp(const Node &A, const Node &B) { return A.x == B.x ? A.y + f[A.id] < B.y + f[B.id] : A.x < B.x;}inline int dcmp(double x) { return x < -eps ? -1 : x < eps ? 0 : 1;}inline LL line(const Vector &P, LL k) { return P.y - k*P.x; } //void CDQ(int l, int r) { if(l == r) { f[l] = max(f[l], f[l-1]); return; } int mid = (l + r) >> 1; CDQ(l, mid); int n = 0, s = 0, t = 0; for(int i = l; i <= mid; ++i) if(f[a[i].id] >= a[i].p) p[++n] = Vector(a[i].x, a[i].y + f[a[i].id]); for(int i = 1; i <= n; ++i) { while(s+1 < t && dcmp((Q[t-1]-Q[t-2]) * (p[i]-Q[t-2])) >= 0) --t; Q[t++] = p[i]; } for(int i = mid+1; i <= r; ++i) { while(s+1 < t && line(Q[s+1], -a[i].d) >= line(Q[s], -a[i].d)) ++s; if(s < t) f[i] = max(f[i], line(Q[s], -a[i].d)); } CDQ(mid+1, r); int cur1 = l, cur2 = mid+1; for(int i = l; i <= r; ++i) { if(cur2 > r || (cur1 <= mid && cmp(a[cur1], a[cur2]))) tmp[i] = a[cur1++]; else tmp[i] = a[cur2++]; } for(int i = l; i <= r; ++i) a[i] = tmp[i];}int n, D, kase;int main () { while(read(n), read(f[0]), read(D), n+f[0]+D) { for(int i = 1; i <= n; ++i) a[i].init(); a[++n].d = D + 1; sort(a + 1, a + n + 1, cmpD); for(int i = 1; i <= n; ++i) a[i].id = i, f[i] = 0; CDQ(1, n); printf("Case %d: %lld\n", ++kase, f[n]); }}//f[i] = f[j] - p[j] + r[j] + (D[i]-D[j]-1)*G[j]//f[i] + (-D[i])*G[j] = f[j] - p[j] + r[j] - (D[j]+1)*G[j]
^
compilation terminated.
|
