제출 #1130512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130512		am_aadvik	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	22 / 100	1096 ms	328 KiB

skyscraper

#include <iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<math.h>
#define int long long
const int inf = 1e17;
const int maxn = 300005;
const int mod = (int)1e9 + 7;
using namespace std;

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

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

	for (int i = 0; i < n; ++i)
		for (auto x : d) {
			for (int i = x.first, val = 0; i >= 0; i -= x.second, ++val)
				ans[x.first] = min(ans[x.first], ans[i] + val);
			for (int i = x.first, val = 0; i < n; i += x.second, ++val)
				ans[x.first] = min(ans[x.first], ans[i] + val);
		}
	cout << ((ans[d[0].first] == inf) ? -1 : ans[d[0].first]);
}

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