제출 #1357242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357242		crispxx	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	504 ms	71212 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

const int inf = 1e9 + 5;

bool chmin(int &a, const int &b) {
	return a > b ? a = b, true : false;
}

const int N = 30000, B = 180;

vector<array<int, 3>> adj[N];

int b[N], p[N], d[N][B];

void solve() {
	int n, m; cin >> n >> m;
	
	for(int i = 0; i < m; i++) {
		cin >> b[i] >> p[i];
		
		if(p[i] < B) {
			adj[b[i]].push_back({b[i], p[i], 0});
		} else {
			for(int j = b[i], cur = 0; j < n; j += p[i], cur++) {
				adj[b[i]].push_back({j, 0, cur});
			}
			for(int j = b[i], cur = 0; j >= 0; j -= p[i], cur++) {
				adj[b[i]].push_back({j, 0, cur});
			}
		}
	}
	
	// (position, 0) = (position)
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < B; j++) {
			d[i][j] = inf;
		}
	}
	
	d[b[0]][0] = 0;
	
	priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
	
	pq.push({0, b[0], 0});
	
	while(!pq.empty()) {
		auto [d_v, pos, pw] = pq.top();
		pq.pop();
		
		// cout << d_v << ' ' << pos << ' ' << pw << nl;
		
		if(d_v != d[pos][pw]) continue;
		
		if(pw == 0) {
			for(auto [npos, npw, w] : adj[pos]) {
				if(chmin(d[npos][npw], d[pos][pw] + w)) {
					pq.push({d[npos][npw], npos, npw});
				}
			}
		} else {
			
			if(pos + pw < n && chmin(d[pos + pw][pw], d[pos][pw] + 1)) {
				pq.push({d[pos + pw][pw], pos + pw, pw});
			}
			
			if(pos - pw >= 0 && chmin(d[pos - pw][pw], d[pos][pw] + 1)) {
				pq.push({d[pos - pw][pw], pos - pw, pw});
			}
			
			if(chmin(d[pos][0], d[pos][pw])) {
				pq.push({d[pos][0], pos, 0});
			}
			
		}
	}
	
	int ans = d[b[1]][0];
	
	if(ans == inf) ans = -1;
	
	cout << ans << nl;
}

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

• 서브태스크 1: 10 / 10
• 서브태스크 2: 12 / 12
• 서브태스크 3: 14 / 14
• 서브태스크 4: 21 / 21
• 서브태스크 5: 43 / 43