제출 #603032

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

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=(1e9)+10;
int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	ll n, m, i, j;
	cin>>n>>m;
	vector<ll> p(m);
	vector<ll> b(m);
	vector<ll> g(n, -1);
	for(i=0; i<m; i++){
		cin>>b[i]>>p[i];
		g[b[i]]=i;
	}
	vector<vector<pair<ll, ll>>> v(n);
	for(i=0; i<m; i++){
		for(j=b[i]%p[i]; j<n; j+=p[i]){
			if(g[j]==-1 || i==j) continue;
			v[b[i]].push_back({j, (abs(b[i]-j))/p[i]});
		}
	}
	
	vector<ll> dp(n, inf);
	
	set<pair<ll, ll>> s;
	dp[b[0]]=0;
	s.insert({0, b[0]});
	
	while(!s.empty()){
		pair<ll, ll> k1=(*s.begin());
		ll a1=k1.first, a2=k1.second;
		s.erase(s.begin());
		for(auto pa: v[a2]){
			ll p1=pa.first, p2=pa.second;
			if(dp[p1]>a1+p2){
				dp[p1]=a1+p2;
				s.insert({dp[p1], p1});
			}
		}
	}
	
	if(dp[b[1]]==inf) cout<<-1;
	else cout<<dp[b[1]];
	
	return 0;
}

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