Submission #235633

#	Time	Username	Problem	Language	Result	Execution time	Memory
235633		Haunted_Cpp	Salesman (IOI09_salesman)	C++17	17 / 100	102 ms	4732 KiB

salesman

/**
 *  author: Duarte Nobrega
 *  created: 28.05.2020    
**/

#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

const int N = 5e5 + 5;

i64 dp [N];
tuple<int, int, int> feiras [N];

int n_feiras, descer, subir, inicio;

i64 solve (int p = 0) {
  i64 &res = dp[p];
  if (~res) return res;
  int where_am_i = get<1>(feiras[p]); 
  if (where_am_i > inicio) {
    res = - 1LL * (where_am_i - inicio) * descer;
  } else {
    res = - 1LL * (inicio - where_am_i) * subir;
  } 
  for (int i = p + 1; i < n_feiras; i++) {
    int final_location = get<1>(feiras[i]);
    int d = abs (final_location - where_am_i);
    if (final_location < where_am_i) {
      res = max (res, solve (i) - 1LL * d * descer + get<2>(feiras[i]));
    } else {
      res = max (res, solve (i) - 1LL * d * subir + get<2>(feiras[i]));
    }
  }
  return res;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n_feiras >> descer >> subir >> inicio;
  assert (n_feiras <= 5000);
  memset (dp, -1, sizeof(dp));
  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 ) {
    if (get<0>(primeiro) != get<0>(segundo)) {
      return get<0>(primeiro) < get<0>(segundo);
    }
    if (descer > subir) {
      return get<1>(primeiro) > get<1>(segundo);
    }
    return get<1>(primeiro) < get<1>(segundo);
  });
  cout << solve () << '\n';
  return 0;
}

• Subtask 1: 17 / 100