oj.uz

답안 #505121

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
505121 2022-01-10T15:34:30 Z blue Salesman (IOI09_salesman) C++17
100 / 100
 591 ms 44220 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
const int mx = 500'001;
const ll INF = 1'000'000'000'000'000'000LL;
using vll = vector<ll>;
#define sz(x) int(x.size())

struct fair
{
    ll l;
    ll m;
};

bool operator < (fair A, fair B)
{
    return A.l < B.l;
}




vector<fair> F[1+mx];


const int Z = (1<<19);

struct segtree
{
    vll val = vll(Z<<1, -INF);

    void update(int I, ll V)
    {
        val[Z+I] = max(val[Z+I], V);
        for(int i = (Z+I)>>1; i >= 1; i >>= 1)
            val[i] = max(val[2*i], val[2*i+1]);
    }

    ll rangemax(ll L, ll R)
    {
        L += Z;
        R += Z+1;
        ll ans = -INF;
        while(L < R)
        {
            if(L & 1)
            {
                ans = max(ans, val[L]);
                L++;
            }
            if(R & 1)
            {
                R--;
                ans = max(ans, val[R]);
            }
            L >>= 1;
            R >>= 1;
        }
        return ans;
    }
};



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    ll U, D;
    ll S;
    cin >> N >> U >> D >> S;

    for(int i = 1; i <= N; i++)
    {
        ll t, l, m;
        cin >> t >> l >> m;
        F[t].push_back({l, m});
    }
    F[mx].push_back({S, 0});

    for(int t = 1; t <= mx; t++) sort(F[t].begin(), F[t].end());

    segtree goleft, goright;
    goleft.update(S, -U*S + 0);
    goright.update(S, +D*S + 0);

    for(int t = 1; t <= mx; t++)
    {
        int q = sz(F[t]);
        if(q == 0) continue;
        vll dp(q);
        for(int i = 0; i < q; i++)
        {
            dp[i] = max(goleft.rangemax(F[t][i].l, mx) + F[t][i].l*U, goright.rangemax(1, F[t][i].l) - F[t][i].l * D);
        }
        for(int i = 1; i < q; i++)
        {
            dp[i] = max(dp[i], dp[i-1]  - D * (F[t][i].l - F[t][i-1].l));
        }
        for(int i = q-2; i >= 0; i--)
        {
            dp[i] = max(dp[i], dp[i+1] - U*(F[t][i+1].l - F[t][i].l));
        }

        vll dpl = dp, dpr = dp;

        dpl[0] = dp[0] + F[t][0].m;
        for(int i = 1; i < q; i++)
        {
            dpl[i] = max(dp[i], dpl[i-1] - D * (F[t][i].l - F[t][i-1].l)) + F[t][i].m;
        }

        dpr[q-1] = dp[q-1] + F[t][q-1].m;
        for(int i = q-2; i >= 0; i--)
        {
            dpr[i] = max(dpr[i], dpr[i+1] - U * (F[t][i+1].l - F[t][i].l)) + F[t][i].m;
        }

        for(int i = 0; i < q; i++)
        {
            goleft.update(F[t][i].l, max(dpl[i], dpr[i]) - U*F[t][i].l);
            goright.update(F[t][i].l, max(dpl[i], dpr[i]) + D*F[t][i].l);
        }
        // for(int i = 1; i < q; i++)
        // {
        //     dp[i] = max(dp[i], dp[i-1] + )
        // }

    }

    cout << goright.rangemax(S, S) - D*S << '\n';
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 28364 KB Output is correct
2 Correct 16 ms 28420 KB Output is correct
3 Correct 15 ms 28460 KB Output is correct
4 Correct 18 ms 28492 KB Output is correct
5 Correct 22 ms 28592 KB Output is correct
6 Correct 35 ms 29144 KB Output is correct
7 Correct 68 ms 29992 KB Output is correct
8 Correct 120 ms 31496 KB Output is correct
9 Correct 197 ms 33064 KB Output is correct
10 Correct 315 ms 37856 KB Output is correct
11 Correct 357 ms 37840 KB Output is correct
12 Correct 457 ms 40996 KB Output is correct
13 Correct 489 ms 41000 KB Output is correct
14 Correct 591 ms 44128 KB Output is correct
15 Correct 504 ms 44220 KB Output is correct
16 Correct 581 ms 44124 KB Output is correct
17 Correct 17 ms 28364 KB Output is correct
18 Correct 21 ms 28504 KB Output is correct
19 Correct 17 ms 28492 KB Output is correct
20 Correct 17 ms 28440 KB Output is correct
21 Correct 20 ms 28544 KB Output is correct
22 Correct 18 ms 28620 KB Output is correct
23 Correct 18 ms 28560 KB Output is correct
24 Correct 18 ms 28544 KB Output is correct
25 Correct 79 ms 30552 KB Output is correct
26 Correct 147 ms 33152 KB Output is correct
27 Correct 272 ms 36928 KB Output is correct
28 Correct 257 ms 36596 KB Output is correct
29 Correct 381 ms 37628 KB Output is correct
30 Correct 335 ms 40368 KB Output is correct