标题党，其因 $Subtask$ 。

斜率优化求助...

$WA$ $on$ #10 #12

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MaxSize = 20;

char buf[1 << MaxSize], *p1, *p2;

#define GetChar() \
    ((p1 == p2) ? (p2 = buf + fread(p1 = buf, 1, 1 << MaxSize, stdin), p1 == p2 ? EOF : *p1++) : *p1++)

template <class T>
inline void in(T &x) {
    x = 0;
    register bool f = 0;
    register char c = GetChar();
    while (c < 47 || c > 58)
        f |= (c == '-'), c = GetChar();
    while (c > 46 && c < 59)
        x = (x << 3) + (x << 1) + (c & 15), c = GetChar();
    x = f ? (~x + 1) : x;
}

const int N = 1e6 + 6;

int n, q[N];

LL f[N], sum[N], dis[N], res[N], pay[N];

inline LL Top(int j, int k) {
	return f[j] - res[j] + sum[j] * dis[j] - (f[k] - res[k] + sum[k] * dis[k]);
}

inline LL Don(int j, int k) {
	return sum[j] - sum[k];
}

signed main() {
	in(n);
	for (register int i = 1, x, p, c; i <= n; ++i) {
		in(x), in(p), in(c);
		dis[i] = x;
		sum[i] = sum[i - 1] + p;
		pay[i] = c;
		res[i] = res[i - 1] + (dis[i] - dis[i - 1]) * sum[i - 1];
	}
    int l = 0, r = 1;
	for (register int i = 1, j; i <= n; ++i) {
//      while (l + 1 < r && Top(q[l + 1], q[l]) <= dis[i] * Don(q[l + 1], q[l]))
		while (l + 1 < r && (double) 1.0 * Top(q[l + 1], q[l]) / Don(q[l + 1], q[l]) <= (double) 1.0 * dis[i])
            ++l;
        j = q[l];
        f[i] = f[j] + res[i] - res[j] - sum[j] * (dis[i] - dis[j]) + pay[i];
//      while (l + 1 < r && Top(i, q[r - 1]) * Don(q[r - 1], q[r - 2]) <= Top(q[r - 1], q[r - 2]) * Don(i, q[r - 1]))
		while (l + 1 < r && (double) 1.0 * Top(i, q[r - 1]) / Don(i, q[r - 1]) <= (double) 1.0 * Top(q[r - 1], q[r - 2]) / Don(q[r - 1], q[r - 2]))
            --r;
        q[r] = i;
        r++;
    }
    printf("%lld\n", f[n]);
	return 0;
}