Submission #198941

#TimeUsernameProblemLanguageResultExecution timeMemory
198941SamAndSalesman (IOI09_salesman)C++17
90 / 100
1032 ms49400 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 500005, m = 500001, INF = 1000000009;
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);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
    //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)
    {
        sort(v[i].begin(), v[i].end(), so1);
        for (int j = 0; j < v[i].size(); ++j)
            ansv[j] = -INF;
        for (int j = 0; j < v[i].size(); ++j)
            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 < v[i].size(); ++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)v[i].size() - 1; j >= 0; --j)
        {
            if (j != (int)v[i].size() - 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 < v[i].size(); ++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;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:86:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
salesman.cpp:88:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
salesman.cpp:91:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
salesman.cpp:112:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
salesman.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &d, &u, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].t, &a[i].x, &a[i].m);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...