제출 #1016293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016293		Muhammet	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	1372 KiB

skyscraper

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

#define N 30005
#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

ll T, n, m, b[N], p[N], vis[N];

vector <int> v[N];

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;

	vector <ll> a(n,1e9);

	for(int i = 0; i < m; i++){
		cin >> b[i] >> p[i];
		v[b[i]].push_back(i);
	}

	set <int> s;
	a[0] = 0;
	s.insert(0);
	ll ans = 1e9;
	while(sz(s) > 0){
		int x = *s.begin();
		s.erase(s.begin());
		for(int i = b[x]-p[x]; i >= 0; i -= p[x]){
			a[i] = (a[i+p[x]] + 1);
			if(vis[i] == 0){
				vis[i] = 1;
				for(auto j : v[i]){
					s.insert(j);
				}
			}
		}
		for(int i = b[x]+p[x]; i < n; i += p[x]){
			a[i] = (a[i-p[x]] + 1);
			if(vis[i] == 0){
				vis[i] = 1;
				for(auto j : v[i]){
					s.insert(j);
				}
			}
		}
		ans = min(ans,a[b[1]]);
	}

	cout << ans;
	return 0;
}

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