제출 #946163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946163		stdfloat	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	10 / 100	1 ms	504 KiB

skyscraper

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

using ll = long long;

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<int> X(m), P(n);
	for (int i = 0; i < m; i++)
		cin >> X[i] >> P[X[i]];

	vector<int> dis(n, INT_MAX); dis[X[0]] = 0;
	priority_queue<pair<int, int>> q; q.push({0, X[0]});
	while (!q.empty()) {
		auto [d, x] = q.top(); q.pop();
	
		if (x == X[1]) return cout << dis[x], 0;

		if (-d != dis[x]) continue;

		for (int i = x; i > 0; i -= P[x]) {
			if (P[i] && dis[x] + (x - i) / P[x] < dis[i]) {
				dis[i] = dis[x] + (x - i) / P[x];
				q.push({-dis[i], i});
			}
		}
		for (int i = x; i < n; i += P[x]) {
			if (P[i] && dis[x] + (i - x) / P[x] < dis[i]) {
				dis[i] = dis[x] + (i - x) / P[x];
				q.push({-dis[i], i});
			}
		}
	}

	cout << -1;
}

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