Submission #1214203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214203		kunzaZa183	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	861 ms	50344 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
const int k = 300;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  int n, m;
  cin >> n >> m;

  vector<pair<int, int>> vpii(m);

  for (auto &a : vpii) cin >> a.first >> a.second;

  vector<vector<int>> dp(n, vector<int>(k, INT_MAX)), out(n);

  for (int i = 0; i < m; i++) out[vpii[i].first].push_back(i);

  // steps, cur, power
  priority_queue<array<int, 3>> pqpii;

  pqpii.push({0, vpii[0].first, 0});

  while (!pqpii.empty()) {
    auto [steps, cur, power] = pqpii.top();
    pqpii.pop();

    steps = -steps;

    if (dp[cur][power] <= steps) continue;

    dp[cur][power] = steps;

    if (dp[cur][0] > steps || power == 0) {
      dp[cur][0] = steps;

      for (auto a : out[cur])
        if (vpii[a].second >= k) {
          for (int i = cur % vpii[a].second; i < n; i += vpii[a].second) {
            int news = steps + abs(i - cur) / vpii[a].second;
            if (i != cur && dp[i][0] == INT_MAX) {
              pqpii.push({-news, i, 0});
            }
          }
        } else {
          dp[cur][vpii[a].second] = steps;

          int newr = cur + vpii[a].second;
          if (newr < n && dp[newr][vpii[a].second] == INT_MAX) {
            pqpii.push({-steps - 1, newr, vpii[a].second});
          }

          int newl = cur - vpii[a].second;
          if (newl >= 0 && dp[newl][vpii[a].second] == INT_MAX) {
            pqpii.push({-steps - 1, newl, vpii[a].second});
          }
        }
    }

    if (power != 0) {
      int newr = cur + power;
      if (newr < n && dp[newr][power] == INT_MAX) {
        pqpii.push({-steps - 1, newr, power});
      }

      int newl = cur - power;
      if (newl >= 0 && dp[newl][power] == INT_MAX) {
        pqpii.push({-steps - 1, newl, power});
      }
    }
  }

  int x = dp[vpii[1].first][0];
  if (x == INT_MAX) {
    cout << "-1\n";
  } else {
    cout << x << "\n";
  }
}

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