Submission #235977

#	Time	Username	Problem	Language	Result	Execution time	Memory
235977		Haunted_Cpp	Salesman (IOI09_salesman)	C++17	15 / 100	52 ms	640 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];

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  // Solution for 15 points
  int n_feiras, descer, subir, inicio;
  cin >> n_feiras >> descer >> subir >> 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);
  });
  auto custo_viagem = [&] ( int st, int et) {
    int custo = (st < et ? subir * (et - st) : descer * (st - et) );
    return custo;
  };
  int mx = 0;
  dp[0] = 0;
  for (int i = 1; i < n_feiras; i++) {
    dp[i] = - 1e9;
    for (int j = i - 1; j >= 0; j--) {
      dp[i] = max (dp[i], dp[j] - custo_viagem (get<1> (feiras[j]), get<1> (feiras[i]) ) + get<2> (feiras[i]) );
    }
    mx = max (mx, dp[i] - custo_viagem (get<1> (feiras[i]), get<1> (feiras[0])));
  }
  cout << mx << '\n';
  return 0;
}

• Subtask 1: 15 / 100