Submission #1159494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159494		pinbu	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	310 ms	260524 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];
const int D = N * 50; vector<array<int, 2>> pq[D];
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;
	pq[0].push_back({b[0], p[0]});
	for (int di = 0; di < D; di++) {
		while (pq[di].size()) {
			auto t = pq[di].back();
			int i = t[0], po = t[1];
			pq[di].pop_back();
			if (di != d[i][po]) continue;
			if (po) {
				if (i + po < n && mini(d[i + po][po], di + 1)) {
					pq[d[i + po][po]].push_back({i + po, po});
				}
				if (i - po >= 0 && mini(d[i - po][po], di + 1)) {
					pq[d[i - po][po]].push_back({i - po, po});
				}
				if (mini(d[i][0], di)) {
					pq[d[i][0]].push_back({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[d[i_][po_]].push_back({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