Submission #1180312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180312		avighna	Train (APIO24_train)	C++20	0 / 100	1121 ms	849716 KiB

train

#include "train.h"

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

const long long inf = 1e15;

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) {
  std::map<std::pair<int, int>,
           std::vector<std::pair<std::pair<int, int>, int>>>
      adj;
  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::set<std::pair<int, long long>>>>(
             max_time + 1));
  for (int i = 0; i < N; ++i) {
    std::set<std::pair<int, long long>> init_meals;
    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.insert({j, t_val});
      tot += t_val;
    }
    if (i != N - 1) {
      tot += (long long)W * inf;
    }
    dp[i][max_time] = {tot, init_meals};
  }
  std::vector<std::set<int>> meals(max_time + 1);
  std::set<int> meals_rn;
  for (int t = max_time; t >= 0; --t) {
    for (auto &i : meals_add[t]) {
      meals_rn.insert(i);
    }
    for (int i = t; i <= max_time; ++i) {
      for (auto &j : meals_rn) {
        meals[i].insert(j);
      }
    }
    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;
          }
          auto it = meals_had.lower_bound({j, -1});
          long long t_val = T[i];
          if (it != meals_had.end() and it->first == j) {
            t_val = std::min(t_val, it->second);
            meals_had.erase(it);
            cost -= it->second;
          }
          meals_had.insert({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 (auto &i : meals[u.second]) {
          auto it = meals_had.lower_bound({i, -1});
          if (it != meals_had.end() and it->first == i) {
            meals_had.erase(it);
            cost -= it->second;
          }
          meals_had.insert({i, 0});
        }
        for (int j = 0; j < W; ++j) {
          if (L[j] > t or t > R[j]) {
            continue;
          }
          auto it = meals_had.lower_bound({j, -1});
          long long t_val = T[i];
          if (it != meals_had.end() and it->first == j) {
            t_val = std::min(t_val, it->second);
            meals_had.erase(it);
            cost -= it->second;
          }
          meals_had.insert({j, t_val});
          cost += t_val;
        }
        dp[i][t] = std::min(dp[i][t], {cost, meals_had});
      }
    }
    for (auto &i : meals_remove[t]) {
      meals_rn.erase(i);
    }
  }
  // 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