Submission #1130629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130629		am_aadvik	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1095 ms	836 KiB

skyscraper

#include <iostream>
#include<vector>
const int inf = 1e9;
using namespace std;

class doge {
public:
	int i, p;
	doge(int x, int y) { i = x, p = y; }
};

int ans[2005];
vector<doge> d;
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, m; cin >> n >> m;
	for (int i = 0; i <= n; ++i)
		ans[i] = inf;

	for (int i = 0; i < m; ++i) {
		int x, y; cin >> x >> y;
		if (i == 1) ans[x] = 0;
		doge c(x, y); d.push_back(c);
	}

	for (int i = 0; i < m; ++i)
		if (!(abs(d[i].i - d[1].i) % d[i].p))
			ans[d[i].i] = abs(d[i].i - d[1].i) / d[i].p;

	bool c = 1;
	for (int j = 0; ((j < n) && c); ++j) {
		c = 0;
		for (auto x : d) {
			for (int i = x.i, val = 0; i >= 0; i -= x.p, ++val)
				if (ans[x.i] > (ans[i] + val)) ans[x.i] = ans[i] + val, c = 1;
			for (int i = x.i, val = 0; i < n; i += x.p, ++val)
				if (ans[x.i] > (ans[i] + val)) ans[x.i] = ans[i] + val, c = 1;
		}
	}
	cout << ((ans[d[0].i] == inf) ? -1 : ans[d[0].i]);
}

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