Submission #695198

#	Time	Username	Problem	Language	Result	Execution time	Memory
695198		NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	239 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long 
using namespace std; 

const int M = 300004;

int n, m;
int ans;
int b[M];
int p[M];
int cost[M];
vector<pair<int, int>> g[M];

inline void dij() {
  memset(cost, -1, sizeof cost);
  cost[b[0]] = 0; 
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int >>> pq; 
  pq.emplace(0, b[0]);
  while (!pq.empty()) {
    auto src = pq.top();
    assert(src.second < M);
    pq.pop();
    if (cost[src.second] != src.first) {
      continue;
    }
    if (src.second == b[1]) {
      ans = min(ans, src.first);
    }
    for (auto [u, w] : g[src.second]) {
      assert(u < M);
      if (cost[u] == -1 || cost[u] > src.first + w) {
        cost[u] = src.first + w;
        pq.emplace(cost[u], u);
      }
    }
  }
}

signed main() {
  ans = INT_MAX;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> p[i];
    assert(b[i] < M);
    for (int j = 1; j < n; ++j) {
      int r = b[i] + j * p[i];
      int l = b[i] - j * p[i];
      if (l >= 0){ 
        g[b[i]].emplace_back(l, j);
      }
      if (r < n) {
        g[b[i]].emplace_back(r, j); 
      }
    }
  }
  dij();
  cout << (ans == INT_MAX ? -1 : ans) << '\n';
  return 0; 
}

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