제출 #1159491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159491		pinbu	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	724 ms	197832 KiB

skyscraper

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

const int N = 30005, B = 175, oo = 1e9 + 7;
bool mini(int &X, int Y) {
	return (X > Y) ? X = Y, true : false;
}

int n, m, b[N], p[N];
vector<array<int, 3>> adj[N][B + 5]; int d[N][B + 5];
void solve(void) {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> b[i] >> p[i];
		if (p[i] > B) {
			for (int pos = b[i] + p[i], w = 1; pos < n; pos += p[i], w++) {
				adj[b[i]][0].push_back({pos, 0, w});
			}
			for (int pos = b[i] - p[i], w = 1; pos >= 0; pos -= p[i], w++) {
				adj[b[i]][0].push_back({pos, 0, w});
			}
		} else {
			adj[b[i]][0].push_back({b[i], p[i], 0});
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= B; j++) {
			d[i][j] = oo;
		}
	}
	d[b[0]][p[0]] = 0;
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
	pq.push({0, b[0], p[0]});
	while (pq.size()) {
		auto t = pq.top();
		int di = t[0], i = t[1], po = t[2];
		pq.pop();
		if (di != d[i][po]) continue;
		if (po) {
			if (i + po < n && mini(d[i + po][po], di + 1)) {
				pq.push({d[i + po][po], i + po, po});
			}
			if (i - po >= 0 && mini(d[i - po][po], di + 1)) {
				pq.push({d[i - po][po], i - po, po});
			}
			if (mini(d[i][0], di)) {
				pq.push({d[i][0], i, 0});
			}
		}
		for (auto V: adj[i][po]) {
			int i_ = V[0], po_ = V[1], w = V[2];
			if (mini(d[i_][po_], di + w)) {
				pq.push({d[i_][po_], i_, po_});
			}
		}
	}
	
	int ans = oo;
	for (int po = 0; po <= B; po++) {
		mini(ans, d[b[1]][po]);
	}
	if (ans == oo) ans = -1;
	cout << ans;
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    solve();
    
    return 0;
}

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