oj.uz

답안 #141525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141525 2019-08-08T09:59:36 Z darkkcyan Salesman (IOI09_salesman) C++14
100 / 100
 613 ms 44592 KB 
#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
    // return (T)(rng() % range);
// }

template<bool is_rev>
struct MaxBit {
    vector<llong> data;
    MaxBit(int n, llong init_val = 0) : data(n + 10, init_val) {}

    void upd(int i, llong val) {
        if (is_rev) i = len(data) - i - 1;
        for (++i; i < len(data); i += i & -i) data[i] = max(data[i], val);
    }

    llong get(int i, llong ans = 0) {
        if (is_rev) i = len(data) - i - 1;
        for (++i; i > 0; i -= i & -i) ans = max(ans, data[i]);
        return ans;
    }
};

#define maxn 501010
#define inf ((llong)1e13)
int n;
llong u, d;
int s;
vector<pair<int, int>> fairs[maxn];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> u >> d >> s;
    rep(i, n) {
        int t, l, m; cin >> t >> l >> m;
        fairs[t].emplace_back(l, m);
    }

    MaxBit<false> down_bit(maxn, -inf); 
    MaxBit<true> up_bit(maxn, -inf);

    auto find_max_profit = [&](int pos) {
        return max(down_bit.get(pos, -inf) - pos * d, up_bit.get(pos, -inf) + pos * u);
    };

    auto update = [&](int pos, llong val) {
        down_bit.upd(pos, val + pos * d);
        up_bit.upd(pos, val - pos * u);
    };
    update(s, 0);
    
    rep(fair_time, maxn) {
        auto& cur = fairs[fair_time];
        if (!len(cur)) continue;
        sort(cur.begin(), cur.end());
        vector<llong> cur_ans(len(cur)), max_down(len(cur)), max_up(len(cur));
        rep(i, len(cur))
            cur_ans[i] = find_max_profit(cur[i].xx) + cur[i].yy;

        llong temp_down = -inf;
        rep(i, len(cur)) { 
            max_down[i] = max(cur_ans[i], temp_down - cur[i].xx * d + cur[i].yy);
            temp_down = max(temp_down, max_down[i] + d * cur[i].xx);
        }

        llong temp_up = -inf;
        for (int i = len(cur); i--; ) {
            max_up[i] = max(cur_ans[i], temp_up + cur[i].xx * u + cur[i].yy);
            temp_up = max(temp_up, max_up[i] - cur[i].xx * u);
        }

        rep(i, len(cur)) {
            cur_ans[i] = max(cur_ans[i], max(max_up[i], max_down[i]));
            // clog << group.xx << ' ' << cur[i].xx << ' ' << cur[i].yy << ' ' << cur_ans[i] << endl;
            update(cur[i].xx, cur_ans[i]);
        }
    }

    cout << find_max_profit(s);

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19960 KB Output is correct
2 Correct 20 ms 19964 KB Output is correct
3 Correct 21 ms 19960 KB Output is correct
4 Correct 22 ms 20092 KB Output is correct
5 Correct 23 ms 20216 KB Output is correct
6 Correct 42 ms 20884 KB Output is correct
7 Correct 76 ms 22392 KB Output is correct
8 Correct 151 ms 24960 KB Output is correct
9 Correct 209 ms 27128 KB Output is correct
10 Correct 310 ms 33528 KB Output is correct
11 Correct 360 ms 33272 KB Output is correct
12 Correct 452 ms 37244 KB Output is correct
13 Correct 460 ms 37752 KB Output is correct
14 Correct 609 ms 44592 KB Output is correct
15 Correct 613 ms 43592 KB Output is correct
16 Correct 565 ms 43720 KB Output is correct
17 Correct 20 ms 19960 KB Output is correct
18 Correct 21 ms 20088 KB Output is correct
19 Correct 20 ms 19960 KB Output is correct
20 Correct 21 ms 20088 KB Output is correct
21 Correct 21 ms 19960 KB Output is correct
22 Correct 23 ms 20092 KB Output is correct
23 Correct 23 ms 20088 KB Output is correct
24 Correct 23 ms 20088 KB Output is correct
25 Correct 71 ms 22392 KB Output is correct
26 Correct 146 ms 25616 KB Output is correct
27 Correct 200 ms 28640 KB Output is correct
28 Correct 244 ms 28656 KB Output is correct
29 Correct 275 ms 30516 KB Output is correct
30 Correct 299 ms 34548 KB Output is correct