Submission #527823

#	Time	Username	Problem	Language	Result	Execution time	Memory
527823		mathking1021	Salesman (IOI09_salesman)	C++17	62 / 100	417 ms	37348 KiB

salesman

#include <iostream>
#include <cstdio>
#include <algorithm>
#define PLPLL pair<ll, PLL>
#define PLL pair<ll, ll>
#define F first
#define S second

using namespace std;
typedef long long ll;

const ll M = 1e18;

ll n, m, m1, m2, k;
PLPLL a[500005];
ll base = (1 << 19);
ll seg1[1100005];
ll seg2[1100005];

void update1(ll p, ll q)
{
    p += base;
    seg1[p] = q;
    p /= 2;
    while(p >= 1)
    {
        seg1[p] = max(seg1[p * 2], seg1[p * 2 + 1]);
        p /= 2;
    }
}

void update2(ll p, ll q)
{
    p += base;
    seg2[p] = q;
    p /= 2;
    while(p >= 1)
    {
        seg2[p] = max(seg2[p * 2], seg2[p * 2 + 1]);
        p /= 2;
    }
}

ll query1(ll p, ll q)
{
    p += base;
    q += base;
    ll re = -M;
    while(p < q)
    {
        if(p % 2 == 1) re = max(re, seg1[p]), p++;
        if(q % 2 == 0) re = max(re, seg1[q]), q--;
        p /= 2, q /= 2;
    }
    if(p == q) re = max(re, seg1[p]);
    return re;
}

ll query2(ll p, ll q)
{
    p += base;
    q += base;
    ll re = -M;
    while(p < q)
    {
        if(p % 2 == 1) re = max(re, seg2[p]), p++;
        if(q % 2 == 0) re = max(re, seg2[q]), q--;
        p /= 2, q /= 2;
    }
    if(p == q) re = max(re, seg2[p]);
    return re;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &m1, &m2, &k);
    m = m1 + m2;
    for(ll i = 0; i < n; i++)
    {
        scanf("%lld%lld%lld", &a[i].F, &a[i].S.F, &a[i].S.S);
    }
    sort(a, a + n);
    for(ll i = 1; i < 2 * base; i++) seg1[i] = seg2[i] = -M;
    update1(k, 0 - k * m);
    update2(k, 0);
    for(ll i = 0; i < n; i++)
    {
        ll t1 = query1(a[i].S.F, base - 1);
        ll t2 = query2(0, a[i].S.F);
        ll t3 = t1 + a[i].S.F * m;
        ll t4 = max(t2, t3) + a[i].S.S;
        ll t5 = query1(a[i].S.F, a[i].S.F) + a[i].S.F * m;
        ll t6 = query2(a[i].S.F, a[i].S.F);
        update1(a[i].S.F, max(t5, t4 - a[i].S.F * m));
        update2(a[i].S.F, max(t6, t4));
    }
    printf("%lld\n", max(query1(k, base - 1) + k * m, query2(0, k)));
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%lld%lld%lld%lld", &n, &m1, &m2, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%lld%lld%lld", &a[i].F, &a[i].S.F, &a[i].S.S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 62 / 100