玄学bug(悬棺
查看原帖
玄学bug(悬棺
315205
Kniqht楼主2023/11/12 22:23

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;
}
2023/11/12 22:23
加载中...