제출 #954892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
954892		colossal_pepe	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	1039 ms	3932 KiB

skyscraper

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

const int INF = 1e9;
const int BLK = 200;

int n, m;
vector<int> b, p;
vector<vector<int>> v;

int f(int x, int c, int y) {
	return x + c * y;
}

void addDoge(int i, int pos, int d, vector<vector<int>> &dist, priority_queue<tuple<int, int, int>> &q) {
	if (p[i] < BLK) {
		dist[pos][p[i]] = min(dist[pos][p[i]], -d);
		q.push(make_tuple(d, pos, p[i]));
	} else {
		int l = b[i] - p[i], r = b[i] + p[i], x = 1;
		while (l >= 0 or r < n) {
			if (l >= 0) {
				dist[l][0] = min(dist[l][0], -d + x);
				q.push(make_tuple(d - x, l, 0));
			}
			if (r < n) {
				dist[r][0] = min(dist[r][0], -d + x);
				q.push(make_tuple(d - x, r, 0));
			}
			l -= p[i];
			r += p[i];
			x++;
		}
	}
}
 
int solve() {
	vector<vector<int>> dist(n, vector<int>(BLK, INF));
	priority_queue<tuple<int, int, int>> q;
	dist[b[0]][p[0]] = 0;
	q.push(make_tuple(0, b[0], p[0]));
	while (not q.empty()) {
		auto [d, pos, power] = q.top();
		q.pop();
		if (dist[pos][power] != -d) continue;
		while (not v[pos].empty()) {
			addDoge(v[pos].back(), pos, d, dist, q);
			v[pos].pop_back();
		}
		if (pos + power < n) {
			dist[pos + power][power] = min(dist[pos + power][power], -d + 1);
			q.push(make_tuple(d - 1, pos + power, power));
		}
		if (pos - power >= 0) {
			dist[pos - power][power] = min(dist[pos - power][power], -d + 1);
			q.push(make_tuple(d - 1, pos - power, power));
		}
	}
	int ret = INF;
	for (int i = 0; i < BLK; i++) {
		ret = min(ret, dist[b[1]][i]);
	}
	return ret == INF ? -1 : ret;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	v.resize(n), b.resize(m), p.resize(m);
	cin >> b[0] >> p[0];
	for (int i = 1; i < m; i++) {
		cin >> b[i] >> p[i];
		v[b[i]].push_back(i);
	}
	cout << solve() << '\n';
	return 0;
}

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