汇总hack数据

1
0 0 1

5
0 0 5
3 1 2
5 0 3
7 9 2
9 0 1

2
0 1 1
1 0 2

2
0 100 200
1 0 0

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf ((1ull << 63) - 1)
using namespace std;

const int N = 2e6 + 5;
int n, m, k, cnt;
struct line
{
    int k, b;
    int calc(int x) {
        return k * x + b;
    }
};
struct tree
{
    line l;
    int ls, rs;
} t[N * 4];

#define ls t[k].ls
#define rs t[k].rs

void insert(int &k, int L, int R, line g)
{
    if (!k)
    {
        k = ++cnt;
        // t[k].lazy = 1;
        t[k].l = g;
        return;
    }
    if (L == R)
    {
        if (g.calc(L) < t[k].l.calc(L)) t[k].l = g;
        return;
    }
    int mid = (L + R) >> 1;
    if (g.calc(mid) < t[k].l.calc(mid)) swap(t[k].l, g);

    if (g.k > t[k].l.k) insert(ls, L, mid, g);
    else if (g.k < t[k].l.k) insert(rs, mid + 1, R, g);
}
int find(int k, int L, int R, int x)
{
    if (!k) return inf;
    if (L == R) return t[k].l.calc(x);
    int mid = (L + R) >> 1;
    if (x <= mid) return min(find(ls, L, mid, x), t[k].l.calc(x));
    return min(find(rs, mid + 1, R, x), t[k].l.calc(x));
}

int V = 0;
void update(line g) { insert(k, 0, V, g); }
int ask(int x) { return find(k, 0, V, x); }

struct node
{
    int x, p, c;
} e[N];
int qp[N], qpx[N], dp[N];

void solve()
{
    int n;
    cin >> n;   
    for (int i = 1; i <= n; i++) 
    {
        cin >> e[i].x >> e[i].p >> e[i].c;
        qp[i] = qp[i - 1] + e[i].p;
        qpx[i] = qpx[i - 1] + e[i].p * e[i].x;
        V = max(V, e[i].x);
    }
    dp[0] = 0;
    update({-qp[0], qpx[0] + dp[0]});
    for (int i = 1; i <= n; i++)
    {
        dp[i] = ask(e[i].x) + e[i].c + qp[i - 1] * e[i].x - qpx[i - 1];
        if (e[i].p == 0) dp[i] = min(dp[i - 1], dp[i]); // 添加本行代码以后ac，原因：这个地方没有货物则dp值需要与前一个站点的dp值取min
        update({-qp[i], qpx[i] + dp[i]});
    }
    cout << dp[n] << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1; // cin >> T;
    while (T--) solve();
    return 0;
}