Submission #1127693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127693		juicy	Train (APIO24_train)	C++20	5 / 100	1091 ms	5444 KiB

train

#include <bits/stdc++.h>

#include "train.h"

using namespace std;

#define             fi  first
#define             se  second
#define           left  ___left___
#define          right  ___right___
#define   scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define  print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#ifdef LOCAL
  #include "debug.h"
#else
  #define debug(...) 42
#endif

namespace std {
template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; }
template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; }
template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; }
}

template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

const long long INF = 1e18;

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y, vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {
  vector<int> ordA(M);
  iota(ordA.begin(), ordA.end(), 0);
  sort(ordA.begin(), ordA.end(), [&](int u, int v) {
    return A[u] < A[v];
  });
  auto qry = [&](int i, int j) {
    int res = 0;
    for (int it = 0; it < W; ++it) {
      res += i < L[it] && R[it] < j;
    }
    return res;
  };
  vector<long long> f(M, INF);
  for (int i = 0; i < M; ++i) {
    int id = ordA[i];
    if (X[id] == 0) {
      f[id] = 1LL * T[0] * qry(0, A[id]);
    }
    for (int j = i - 1; j >= 0; --j) {
      int ind = ordA[j];
      if (B[ind] <= A[id] && Y[ind] == X[id]) {
        minimize(f[id], f[ind] + 1LL * T[X[id]] * qry(B[ind], A[id]));
      }
    }
    f[id] = min(INF, f[id] + C[id]);
  }
  const int MAX = 1e9 + 7;
  long long res = INF;
  for (int i = 0; i < M; ++i) {
    if (Y[i] == N - 1) {
      res = min(res, f[i] + 1LL * T[N - 1] * qry(B[i], MAX));
    }
  }
	return res == INF ? -1 : res;
}

// signed main() {
// file("TRAIN");
//   int N, M, W;
//   assert(3 == scanf("%d %d %d", &N, &M, &W));
//   std::vector<int> t(N);
//   std::vector<int> x(M);
//   std::vector<int> y(M);
//   std::vector<int> a(M);
//   std::vector<int> b(M);
//   std::vector<int> c(M);
//   std::vector<int> l(W);
//   std::vector<int> r(W);
//   for (int i = 0; i < N; i++)
//     assert(1 == scanf("%d", &t[i]));
//   for (int i = 0; i < M; i++)
//     assert(5 == scanf("%d %d %d %d %d", &x[i], &y[i], &a[i], &b[i], &c[i]));
//   for (int i = 0; i < W; i++)
//     assert(2 == scanf("%d %d", &l[i], &r[i]));
//   printf("%lld", solve(N, M, W, t, x, y, a, b, c, l, r));
// }

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60