Submission #236001

#	Time	Username	Problem	Language	Result	Execution time	Memory
236001		Haunted_Cpp	Salesman (IOI09_salesman)	C++17	60 / 100	263 ms	12240 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 max_on_suffix>
struct FenwickTree {
  vector<int> bit;
  const int L;
  FenwickTree (int n) : L (n + 5) {
    bit = vector<int> (L, -1e9);
  }
  void update (int idx, int delta) {
    if (max_on_suffix) idx = L - idx;
    for (; idx < L; idx += idx & (- idx)) {
      bit[idx] = max (bit[idx], delta);
    }
  }
  int query (int idx) {
    if (max_on_suffix) idx = L - 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;
  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 (MAX_FEIRAS);
  FenwickTree <false> downstream (MAX_FEIRAS);
  int mx = 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] - (cur < inicio ? descer * (inicio - cur) : subir * (cur - inicio) ) );
  }
  cout << mx << '\n';
  return 0;
}

• Subtask 1: 60 / 100