Submission #695233

#	Time	Username	Problem	Language	Result	Execution time	Memory
695233		NeroZein	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	18 ms	16172 KiB

skyscraper

/*
 *    author: NeroZein
 *    created: 04.02.2023 22:58:06
*/
#include <bits/stdc++.h>
using namespace std;

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

const int N = 2003; 

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

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

int ans;
int cost[N];
inline void dij() {
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; 
	memset(cost, 0x3f3f3f3f, sizeof cost);
	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;
	memset(g, 0x3f3f3f3f, sizeof g);
	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);
			}
		}
	}
	ans = INT_MAX;
	dij();
	cout << -1 << '\n';
	return 0;
}

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