Submission #1180432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180432		avighna	Train (APIO24_train)	C++20	0 / 100	1098 ms	115868 KiB

train

#include "train.h"

#include <algorithm>
// #include <iostream>
// #include <map>
#include <numeric>
// #include <queue>
// #include <set>
#include <vector>

const long long inf = 1e15;

const int N = 1e3 + 1;

std::vector<std::pair<std::pair<int, int>, int>> adj[N][N];

long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X,
                std::vector<int> Y, std::vector<int> A, std::vector<int> B,
                std::vector<int> C, std::vector<int> L, std::vector<int> R) {
  int max_time = 0;
  int max_l_i = 0, max_r_i = 0;
  long long t_max = *std::max_element(T.begin(), T.end());
  for (int i = 0; i < M; ++i) {
    adj[X[i]][A[i]].push_back({{Y[i], B[i]}, C[i]});
    max_time = std::max(max_time, std::max({L[i], R[i], B[i]}));
  }
  std::vector<std::vector<int>> meals_add(max_time + 1),
      meals_remove(max_time + 1);
  for (int i = 0; i < W; ++i) {
    meals_add[R[i]].push_back(i);
    meals_remove[L[i]].push_back(i);
  }

  std::vector dp(N, std::vector<std::pair<long long, std::vector<long long>>>(
                        max_time + 1));
  for (int i = 0; i < N; ++i) {
    std::vector<long long> init_meals(W);
    long long tot = 0;
    for (int j = 0; j < W; ++j) {
      long long t_val = inf;
      if (L[j] <= t_max and t_max <= R[j]) {
        t_val = T[i];
      }
      init_meals[j] = t_val;
      tot += t_val;
    }
    if (i != N - 1) {
      tot += (long long)W * inf;
    }
    dp[i][max_time] = {tot, init_meals};
  }
  std::vector meals(max_time + 1, std::vector<bool>(W));
  std::vector<bool> meals_rn(W);
  for (int t = max_time; t >= 0; --t) {
    for (auto &i : meals_add[t]) {
      meals_rn[i] = true;
    }
    for (int i = t; i <= max_time; ++i) {
      for (int j = 0; j < W; ++j) {
        if (!meals_rn[j]) {
          continue;
        }
        meals[i][j] = true;
      }
    }
    for (int i = 0; i < N; ++i) {
      if (t == max_time) {
        continue;
      }
      dp[i][t] = dp[i][t + 1];
      { // update meals with station i
        auto &meals_had = dp[i][t].second;
        auto &cost = dp[i][t].first;
        for (int j = 0; j < W; ++j) {
          if (L[j] > t or t > R[j]) {
            continue;
          }
          long long t_val = T[i];
          t_val = std::min(t_val, meals_had[j]);
          cost -= meals_had[j];
          meals_had[j] = t_val;
          cost += t_val;
        }
      }
      for (auto &[u, wt] : adj[i][t]) {
        auto &meals_had = dp[u.first][u.second].second;
        long long cost = wt + dp[u.first][u.second].first;
        // take meals maybe
        // time interval: [t, u.second]
        for (int i = 0; i < W; ++i) {
          if (meals[u.second][i]) {
            cost -= meals_had[i];
            meals_had[i] = 0;
          }
        }
        for (int j = 0; j < W; ++j) {
          if (L[j] > t or t > R[j]) {
            continue;
          }
          long long t_val = T[i];
          t_val = std::min(t_val, meals_had[j]);
          cost -= meals_had[j];
          meals_had[j] = t_val;
          cost += t_val;
        }
        if (cost < dp[i][t].first) {
          dp[i][t] = {cost, meals_had};
        }
      }
    }
    for (auto &i : meals_remove[t]) {
      meals_rn[i] = false;
    }
  }
  // dp[0][0] = time 0, city 0
  long long ans = dp[0][0].first;
  if (ans >= inf) {
    ans = -1;
  }
  return ans;
}

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