Submission #235994

#	Time	Username	Problem	Language	Result	Execution time	Memory
235994		Haunted_Cpp	Salesman (IOI09_salesman)	C++17	15 / 100	9 ms	4480 KiB

salesman

/**
 *  author: Duarte Nobrega
 *  created: 30.05.2020    
**/
 
#include <bits/stdc++.h>
using namespace std;

const int MAX_FEIRAS = 5e5 + 5;

int dp [MAX_FEIRAS];
tuple<int, int, int> feiras [MAX_FEIRAS];

template <bool invertido>
struct FenwickTree {
  vector<int> bit;
  FenwickTree () {
    bit = vector<int> (MAX_FEIRAS, -1e9);
  }
  void update (int idx, int delta) {
    if (invertido) idx = MAX_FEIRAS - idx;
    for (; idx < MAX_FEIRAS; idx += idx & (- idx)) {
      bit[idx] = max (bit[idx], delta);
    }
  }
  int query (int idx) {
    if (invertido) idx = MAX_FEIRAS - idx;
    int res = -1e9;
    for (; idx > 0; idx -= idx & (- idx)) {
      res = max (res, bit[idx]);
    }
    return res;
  }
};

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  // Solution for 60 points
  int n_feiras, descer, subir, inicio;
  cin >> n_feiras >> subir >> descer >> inicio;
  assert (n_feiras <= 5000);
  feiras[0] = make_tuple (0, inicio, 0);
  n_feiras++;
  for (int i = 1; i < n_feiras; i++) {
    int dia, onde, lucro;
    cin >> dia >> onde >> lucro;
    feiras[i] = make_tuple(dia, onde, lucro);
  }
  sort (feiras, feiras + n_feiras, [&] ( auto primeiro, auto segundo ) {
    return get<0> (primeiro) < get<0> (segundo);
  });
  FenwickTree <true> upstream;
  FenwickTree <false> downstream;
  auto custo_viagem = [&] ( int st, int et) {
    int custo = (st < et ? descer * (et - st) : subir * (st - et) );
    return custo;
  };
  int mx = -1e9;
  dp[0] = 0;
  upstream.update (inicio, - inicio * subir);
  downstream.update (inicio, + inicio * descer); 
  for (int i = 1; i < n_feiras; i++) { 
    int cur = get<1> (feiras[i]);
    dp[i] = - 1e9;
    // Upstream
    dp[i] = max (dp[i], upstream.query (cur + 1) + cur * subir + get<2> (feiras[i]));
    // Downstream
    dp[i] = max (dp[i],  downstream.query (cur - 1) - cur * descer + get<2> (feiras[i]));
    // Update upstream
    upstream.update ( cur, dp[i] - cur * subir );
    // Update downstream
    downstream.update ( cur, dp[i] + cur * descer );
    mx = max (mx, dp[i] - custo_viagem (get<1> (feiras[i]), get<1> (feiras[0])));
  }
  cout << mx << '\n';
  return 0;
}

• Subtask 1: 15 / 100