제출 #695243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
695243		NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	128 ms	65044 KiB

skyscraper

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2003; 
const int M = 30004; 

int n, m;
int b[M];
int p[M];
int g[N][N];

inline void minSelf(int& x, int y) {
	x = min(x, y); 
}

int cost[N];
inline void dij() {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
	for (int i = 0; i < n; ++i) {
		cost[i] = 1e15;
	}
	cost[b[0]] = 0;
	pq.emplace(0, b[0]);
	while (!pq.empty()) {
		auto src = pq.top(); 
		pq.pop();
		if (src.second == b[1]) {
			cout << src.first << '\n';
			exit(0);
		}
		if (src.first != cost[src.second]) {
			continue; 
		}
		for (int i = 0; i < n; ++i) {
			if (src.first + g[src.second][i] < cost[i]) {
				cost[i] = src.first + g[src.second][i];
				pq.emplace(cost[i], i); 
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			g[i][j] = 1e15;
		}
	}
	for (int i = 0; i < m; ++i) {
		cin >> b[i] >> p[i];
		for (int j = 1; j < n; ++j) {
			int l = b[i] - j * p[i];
			int r = b[i] + j * p[i];
			if (r < n) {
				minSelf(g[b[i]][r], j);
			}
			if (l >= 0) {
				minSelf(g[b[i]][l], j);
			}
		}
	}
	dij();
	cout << -1 << '\n';
	return 0;
}

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