제출 #874518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874518		chadmod	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	491 ms	262144 KiB

skyscraper

/**
 *    author:  NimaAryan
 *    created: 2023-11-17 08:21:07  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int N, M;
  cin >> N >> M;

  vector<int> B(M), P(M);
  for (int i = 0; i < M; ++i) {
    cin >> B[i] >> P[i];
  }

  vector<vector<pair<int, int>>> at(N);
  for (int i = 0; i < M; ++i) {
    for (int x = B[i], t = 0; x < N; x += P[i], ++t) {
      at[x].emplace_back(B[i], t);
    }
    for (int x = B[i], t = 0; x >= 0; x -= P[i], ++t) {
      at[x].emplace_back(B[i], t);
    }
  }

  constexpr int inf = numeric_limits<int>::max();

  vector<int> dist(N, inf);
  dist[B[1]] = 0;

  vector<bool> vis(N);

  for (int it = 0; it < N; ++it) {
    int v = -1;
    for (int u = 0; u < N; ++u) {
      if (!vis[u] && (v == -1 || dist[u] < dist[v])) {
        v = u;
      }
    }
    if (v == -1 || dist[v] == inf) {
      break;
    }
    vis[v] = true;
    for (auto [u, d] : at[v]) {
      dist[u] = min(dist[u], dist[v] + d);
    }
  }

  cout << (vis[B[0]] ? dist[B[0]] : -1) << "\n";

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43