제출 #1357152

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

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

const int inf = 1e9 + 5;

void solve() {
	int n, m; cin >> n >> m;
	
	vector<int> b(m), p(m);
	
	vector<vector<int>> same(n);
	
	for(int i = 0; i < m; i++) {
		cin >> b[i] >> p[i];
		same[b[i]].push_back(i);
	}
	
	vector mod(n, vector(n, vector<int>()));
	
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < m; j++) {
			mod[i][b[j] % i].push_back(j);
		}
	}
	
	vector<int> d(m, inf);
	
	d[0] = 0;
	
	queue<int> q;
	
	q.push(0);
	
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		
		if(p[v] == 0 || p[v] >= n) {
			for(auto to : same[b[v]]) {
				if(d[to] > d[v]) {
					d[to] = d[v];
					q.push(to);
				}	
			}
		} else {
			for(auto to : mod[p[v]][b[v] % p[v]]) {
				int cost = abs(b[to] - b[v]) / p[v];
				
				if(d[to] > d[v] + cost) {
					d[to] = d[v] + cost;
					q.push(to);
				}
			}
		}
	}
	
	if(d[1] == inf) d[1] = -1;
	
	cout << d[1] << nl;
}

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

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