제출 #756110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756110		mingli	Salesman (IOI09_salesman)	C++17	32 / 100	437 ms	65536 KiB

salesman

#include "bits/stdc++.h"

#define ll long long
#define all(x) x.begin(), x.end()
#define read(x) for(auto &i : x) cin >> i;
#define sz(x) (int) (x).size()
#define len(x) (int) (x).length()
#define arr array

constexpr int INF = 1e9 + 9;
constexpr long long INF_LL = 1e18 + 9;
constexpr int MOD = 1e9 + 7; // 998244353;

// up, right, down, left
constexpr int mX_4 [] = {0, 1, 0, -1};
constexpr int mY_4 [] = {-1, 0, 1, 0};

using namespace std;

ll rand_num(ll l, ll r) {
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<ll>(l, r)(gen);
}

template <typename T>
std::ostream& operator<<(std::ostream& _os, const std::pair<T, T>& _p) {
    _os << _p.first << ' ' << _p.second;
    return _os;
}

template <typename T>
void dbg_vec(string str, vector <T> &x) {
    cerr << "DBG " << str << '\n';
    for (int i = 0; i < sz(x); ++i) {
        cerr << "I " << i << " -> " << x[i] << '\n';
    }
    cerr << '\n';
}

const int MAX_BIT_DBG = 3;
void dbg_bits(int n) {
    bitset <MAX_BIT_DBG> v (n);
    cerr << v << '\n';
}

template <typename T>
bool vmin(T &a, T b) { return (a > b ? a = b, true : false); }
 
template <typename T>
bool vmax(T &a, T b) { return (a < b ? a = b, true : false); }

/**
 * (i - j) * c --> dove c è U oppure D
 * Devo trovare velocemente j che mi massimizza la cosa
 * sottraggo ad value[i] i
 * Per ogni valore che vado a computare, sottraggo la posizione di i --> v[j] + j + g - i se i > j
 * Se i < j allora v[j] - j + g + i
 * Posso tenermi 3 segment
 */

struct Segment {
    vector <ll> st;
    int n;

    Segment(int _n) {
        n = _n;
        st.resize(n<<1, -INF_LL);
    }

    ll get(int idx) { return st[idx + n]; }

    // ritorna true se l'update e' servito
    bool upd(int idx, ll updV) {
        idx += n;
        if (vmax(st[idx], updV)) {
            for (; idx > 1; idx >>= 1) {
                st[idx >> 1] = max(st[idx], st[idx ^ 1]);
            }
            return true;
        } 
        return false;
    }

    ll get_max(int l, int r) {
        ll mx = -INF_LL;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) vmax(mx, st[l++]);
            if (r & 1) vmax(mx, st[--r]);                
        }
        return mx;
    }
};

#define int ll

constexpr int MAXN = 520002;

void solve() {
    int n, u, d, s; cin >> n >> u >> d >> s;

    vector <map <int, int> > event (MAXN);

    for (int i = 0; i < n; ++i) {
        int day, pos, reward; cin >> day >> pos >> reward;
        event[day][pos] += reward;
    }

    Segment st(MAXN);
    Segment st_r(MAXN); // utilizzato se la posizione in cui sono e' < di quelli in cui voglio vedere
    Segment st_l(MAXN); // utilizzato se la posizione in cui sono e' > di quelli in cui voglio vedere

    // per up, devo sottrarre la posizione
    // per down, devo aggiungere la posizione

    st.upd(s, 0);
    st_l.upd(s, -s * u);
    st_r.upd(s, s * d);

    for (int day = 1; day < MAXN; ++day) {
        if (sz(event[day]) == 0) continue;
        for (auto [pos, reward] : event[day]) {
            // provo a salire per arrivare a pos --> scelgo i punti < pos dal segment up
            ll mx_L = st_l.get_max(pos, MAXN);
            ll mx_R = st_r.get_max(0, pos + 1);

            // 3 * 20 --> -60 + 110 = 50

            ll cost1 = mx_R + reward - (pos * d); // salgo a destra 
            ll cost2 = mx_L + reward + (pos * u); // salgo in sinistra
            // cerr << "Mx_L " << mx_L << " reward " << reward << " pls " << (pos * u) << endl;
            ll new_sub = max(cost1, cost2);

            // cerr << "Mx_L " << mx_L << " Mx_R " << mx_R << " cost1 " << cost1 << " cost2 " << cost2 << " --> " << new_sub << endl;

            if (st.upd(pos, new_sub)) { // l'update ha migliorato i costi    
                st_r.upd(pos, new_sub + pos * d);
                st_l.upd(pos, new_sub - pos * u);
            }
            // cerr << "Max profitto day: " << day << " --> " << st.get_max(0, MAXN) << '\n';
            // if (day == return;
        }    
    }

    // calcolo la risposta per tornare a casa --> 
    ll ans = 0;
    for (int i = 0; i < MAXN; ++i) {
        if (i == s) {
            vmax(ans, st.get(i));
        } else if (i < s) {
            vmax(ans, st.get(i) - d * (s - i));
        } else {
            vmax(ans, st.get(i) - u * (i - s));
        }
    }

    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tt = 1; // cin >> tt;
    while (tt--) solve();
    return 0;
}

• Subtask 1: 32 / 100