Submission #198944

#	Time	Username	Problem	Language	Result	Execution time	Memory
198944		SamAnd	Salesman (IOI09_salesman)	C++17	100 / 100	968 ms	49528 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
const int N = 500005, m = 500001, INF = 1000000009;

int ka()
{
    int x = 0;
    while (1)
    {
        char y = getchar();
        if ('0' <= y && y <= '9')
            x = (x * 10) + (y - '0');
        else
            return x;
    }
}

struct ban
{
    int t, x, m;
};
bool operator<(const ban& a, const ban& b)
{
    return a.t < b.t;
}
bool so1(const ban& a, const ban& b)
{
    return a.x < b.x;
}

int n;
int d, u;
int s;
ban a[N];

vector<int> t1, t2;

void ubd(vector<int>& t, int tl, int tr, int l, int r, int b, int k, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        t[pos] = max(t[pos], b);
        return;
    }
    int m = (tl + tr) / 2;
    ubd(t, tl, m, l, min(m, r), b, k, pos * 2);
    ubd(t, m + 1, tr, max(m + 1, l), r, b, k, pos * 2 + 1);
}
int qry(vector<int>& t, int tl, int tr, int x, int k, int pos)
{
    if (tl == tr)
    {
        return t[pos] + (k * x);
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        return max(qry(t, tl, m, x, k, pos * 2), t[pos] + (k * x));
    else
        return max(qry(t, m + 1, tr, x, k, pos * 2 + 1), t[pos] + (k * x));
}

void solv1()
{
    sort(a + 1, a + n + 1);
    t1.assign(4 * N, -INF);
    t2.assign(4 * N, -INF);
    ubd(t1, 1, m, 1, s, -s * d, d, 1);
    ubd(t2, 1, m, s, m, s * u, -u, 1);
    for (int i = 1; i <= n; ++i)
    {
        int ans = max(qry(t1, 1, m, a[i].x, d, 1), qry(t2, 1, m, a[i].x, -u, 1)) + a[i].m;
        ubd(t1, 1, m, 1, a[i].x, ans - a[i].x * d, d, 1);
        ubd(t2, 1, m, a[i].x, m, ans + a[i].x * u, -u, 1);
    }
    int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1));
    printf("%d\n", ans);
}

vector<ban> v[N];
int ansv[N];
int qryy[N];
int main()
{
    //freopen("input.txt", "r", stdin);
    //scanf("%d%d%d%d", &n, &d, &u, &s);
    n = ka();
    d = ka();
    u = ka();
    s = ka();
    for (int i = 1; i <= n; ++i)
    {
        //scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
        a[i].t = ka();
        a[i].x = ka();
        a[i].m = ka();
    }
    //solv1();
    for (int i = 1; i <= n; ++i)
        v[a[i].t].push_back(a[i]);
    t1.assign(4 * N, -INF);
    t2.assign(4 * N, -INF);
    ubd(t1, 1, m, 1, s, -s * d, d, 1);
    ubd(t2, 1, m, s, m, s * u, -u, 1);
    for (int i = 1; i < N; ++i)
    {
        if (v[i].empty())
            continue;
        sort(v[i].begin(), v[i].end(), so1);
        int vs = v[i].size();
        for (int j = 0; j < vs; ++j)
        {
            ansv[j] = -INF;
            qryy[j] = max(qry(t1, 1, m, v[i][j].x, d, 1), qry(t2, 1, m, v[i][j].x, -u, 1)) + v[i][j].m;
        }
        int yans = -INF;
        for (int j = 0; j < vs; ++j)
        {
            if (j)
                yans -= (v[i][j].x - v[i][j - 1].x) * u;
            int yansv = -INF;
            yansv = qryy[j];
            yansv = max(yansv, yans + v[i][j].m);
            yans = max(yans, yansv);
            ansv[j] =  max(ansv[j], yansv);
        }
        yans = -INF;
        for (int j = (int)vs - 1; j >= 0; --j)
        {
            if (j != (int)vs - 1)
                yans -= (v[i][j + 1].x - v[i][j].x) * d;
            int yansv = -INF;
            yansv = qryy[j];
            yansv = max(yansv, yans + v[i][j].m);
            yans = max(yans, yansv);
            ansv[j] = max(ansv[j], yansv);
        }
        for (int j = 0; j < vs; ++j)
        {
            int ans = ansv[j];//max(qry(t1, 1, m, a[i].x, d, 1), qry(t2, 1, m, a[i].x, -u, 1)) + a[i].m;
            ubd(t1, 1, m, 1, v[i][j].x, ans - v[i][j].x * d, d, 1);
            ubd(t2, 1, m, v[i][j].x, m, ans + v[i][j].x * u, -u, 1);
        }
    }
    int ans = max(qry(t1, 1, m, s, d, 1), qry(t2, 1, m, s, -u, 1));
    printf("%d\n", ans);
    return 0;
}

• Subtask 1: 100 / 100