Submission #666196

#	Time	Username	Problem	Language	Result	Execution time	Memory
666196		Shahrad	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1097 ms	2460 KiB

skyscraper

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

#define ll long long
#define int ll
#define mk make_pair
#define pii pair<int, int>
#define F first
#define S second
#define sz size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

const int N = 3e4 + 5;

int b[N], p[N], d[N];
set <pii> st;
int n;

void dij ()
{
	int v = st.begin () -> S;
	st.erase (st.begin ());
	for (int i = 0; i < n; i++)
		if (b[v] % p[v] == b[i] % p[v] && d[v] + abs (b[v] - b[i]) / p[v] < d[i])
		{
			st.erase (mk (d[i], i));
			d[i] = d[v] + abs (b[v] - b[i]) / p[v];
			st.insert (mk (d[i], i));
		}
	if (st.sz)
		dij ();
}

void Solve ()
{
	int m;
	cin >> m >> n;
	for (int i = 0; i < n; i++)
		cin >> b[i] >> p[i];
	memset (d, 63, sizeof d);
	d[0] = 0;
	st.insert (mk (d[0], 0));
	dij ();
	if (d[1] == d[N - 1])
		cout << -1 << endl;
	else
		cout << d[1] << endl;
}

int32_t main ()
{
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	int tt = 1;
//	cin >> tt;
	while (tt--)
		Solve ();
}

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