rt,我把注释上面一行换成注释一行就样例1过不去了
这是题解代码,我自己写的样例1寄了,实在看不出问题,就拿题解改了改看什么情况下会同样输出错误的8
#include <cmath>
#include <cstdio>
#include <algorithm>
inline long long read() {
char c = getchar(); long long x = 0;
while (c < '0' || c > '9') { c = getchar(); }
while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c & 15); c = getchar(); }
return x;
}
typedef long long lol;
const int maxN = 2000005;
const double eps = 1e-10;
int n, l, r, q[maxN];
long long ans, f[maxN];
struct Square { lol x, y, w; } s[maxN];
bool operator <(Square x, Square y) { return x.y > y.y; }
inline double getX(int u) { return s[u].x; }
inline double getY(int u) { return f[u]; }
inline double getSlope(int u, int v) { return std::abs(getX(v) - getX(u)) < eps ? 1e10 : (getY(v) - getY(u)) / (getX(v) - getX(u)); }
inline double X(int u) { return s[u].x; }
inline double Y(int u) { return f[u]; }
int main() {
n = read();
for (int i = 1; i <= n; i++) { s[i].x = read(); s[i].y = read(); s[i].w = read() ;}
std::sort(s + 1, s + n + 1);
for (int i = 1; i <= n; i++) {
while (l < r && (getY(q[l]) - getY(q[l+1])) / (getX(q[l]) - getX(q[l+1])) >= s[i].y) { l++; }
//while (l < r && (getY(q[l]) - getY(q[l+1])) >= s[i].y* (getX(q[l]) - getX(q[l+1]))) { l++; }
f[i] = s[i].x * s[i].y - s[i].w;
if (l <= r) { f[i] = std::max(f[i], f[q[l]] + (s[i].x - s[q[l]].x) * s[i].y - s[i].w); }
ans = std::max(ans, f[i]);
while (l < r && (Y(q[r-1])-Y(q[r]))*(X(i)-X(q[r]))<=(Y(i)-Y(q[r]))*(X(q[r-1])-X(q[r]))) { r--; } q[++r] = i;
}
printf("%I64d\n", ans);
return 0;
}