oj.uz

답안 #545683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545683 2022-04-05T07:37:50 Z alextodoran Salesman (IOI09_salesman) C++17
100 / 100
 544 ms 60240 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500000;
const int D_MAX = 500000;
const int L_MAX = 500001;

const ll INF = LLONG_MAX / 2;

int N, L, R, S;

struct Fair {
    int day;
    int pos;
    int profit;
};
bool operator < (const Fair &x, const Fair &y) {
    return x.pos < y.pos;
}

Fair fairs[N_MAX + 2];
vector <int> onDay[D_MAX + 2];
vector <int> days;

ll maxStart[N_MAX + 2];
ll maxProfit[N_MAX + 2];

ll maxPref[L_MAX + 2];
ll maxSuff[L_MAX + 2];
void updatePref (int pos, ll val) {
    for (int i = pos; i >= 1; i -= i & -i) {
        maxSuff[i] = max(maxSuff[i], val);
    }
}
void updateSuff (int pos, ll val) {
    for (int i = pos; i <= L_MAX; i += i & -i) {
        maxPref[i] = max(maxPref[i], val);
    }
}
ll queryPref (int pos) {
    ll ret = -INF;
    for (int i = pos; i >= 1; i -= i & -i) {
        ret = max(ret, maxPref[i]);
    }
    return ret;
}
ll querySuff (int pos) {
    ll ret = -INF;
    for (int i = pos; i <= L_MAX; i += i & -i) {
        ret = max(ret, maxSuff[i]);
    }
    return ret;
}

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

    cin >> N >> L >> R >> S;
    for (int i = 1; i <= N; i++) {
        cin >> fairs[i].day >> fairs[i].pos >> fairs[i].profit;
    }

    sort(fairs + 1, fairs + N + 1);
    for (int i = 1; i <= N; i++) {
        onDay[fairs[i].day].push_back(i);
        days.push_back(fairs[i].day);
    }
    sort(days.begin(), days.end());
    days.resize(unique(days.begin(), days.end()) - days.begin());

    fill(maxPref + 1, maxPref + L_MAX + 1, -INF);
    fill(maxSuff + 1, maxSuff + L_MAX + 1, -INF);
    updatePref(S, 0 - (ll) L * S);
    updateSuff(S, 0 + (ll) R * S);
    for (int d : days) {
        for (int i : onDay[d]) {
            maxStart[i] = max(queryPref(fairs[i].pos) - (ll) R * fairs[i].pos,
                              querySuff(fairs[i].pos) + (ll) L * fairs[i].pos);
        }
        ll currMax = -INF;
        for (int x = 0; x < (int) onDay[d].size(); x++) {
            int i = onDay[d][x];
            if (x > 0) {
                int j = onDay[d][x - 1];
                currMax -= (ll) R * (fairs[i].pos - fairs[j].pos);
            }
            currMax = max(currMax, maxStart[i]) + fairs[i].profit;
            maxProfit[i] = currMax;
        }
        currMax = -INF;
        for (int x = (int) onDay[d].size() - 1; x >= 0; x--) {
            int i = onDay[d][x];
            if (x < (int) onDay[d].size() - 1) {
                int j = onDay[d][x + 1];
                currMax -= (ll) L * (fairs[j].pos - fairs[i].pos);
            }
            currMax = max(currMax, maxStart[i]) + fairs[i].profit;
            maxProfit[i] = max(maxProfit[i], currMax);
        }
        for (int i : onDay[d]) {
            updatePref(fairs[i].pos, maxProfit[i] - (ll) L * fairs[i].pos);
            updateSuff(fairs[i].pos, maxProfit[i] + (ll) R * fairs[i].pos);
        }
    }

    ll answer = 0;
    for (int i = 1; i <= N; i++) {
        if (fairs[i].pos < S) {
            maxProfit[i] -= (ll) (S - fairs[i].pos) * R;
        } else {
            maxProfit[i] -= (ll) (fairs[i].pos - S) * L;
        }
        answer = max(answer, maxProfit[i]);
    }
    cout << answer << "\n";

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19924 KB Output is correct
2 Correct 12 ms 19796 KB Output is correct
3 Correct 11 ms 20052 KB Output is correct
4 Correct 12 ms 20052 KB Output is correct
5 Correct 14 ms 20180 KB Output is correct
6 Correct 26 ms 21408 KB Output is correct
7 Correct 56 ms 23812 KB Output is correct
8 Correct 107 ms 28028 KB Output is correct
9 Correct 172 ms 31560 KB Output is correct
10 Correct 244 ms 43456 KB Output is correct
11 Correct 340 ms 43960 KB Output is correct
12 Correct 426 ms 51064 KB Output is correct
13 Correct 416 ms 51300 KB Output is correct
14 Correct 544 ms 60240 KB Output is correct
15 Correct 425 ms 59328 KB Output is correct
16 Correct 525 ms 59188 KB Output is correct
17 Correct 11 ms 19796 KB Output is correct
18 Correct 11 ms 19924 KB Output is correct
19 Correct 12 ms 19924 KB Output is correct
20 Correct 11 ms 20032 KB Output is correct
21 Correct 11 ms 20024 KB Output is correct
22 Correct 13 ms 20180 KB Output is correct
23 Correct 12 ms 20084 KB Output is correct
24 Correct 13 ms 20092 KB Output is correct
25 Correct 66 ms 24976 KB Output is correct
26 Correct 127 ms 30048 KB Output is correct
27 Correct 204 ms 37472 KB Output is correct
28 Correct 234 ms 38460 KB Output is correct
29 Correct 316 ms 44712 KB Output is correct
30 Correct 331 ms 45640 KB Output is correct