제출 #905719

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

skyscraper

#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int NP=3e4+10;
const int NP1=2e3+10;
const int inf=1e9;
int dist[NP1];
int b[NP],p[NP];
vector<pair<int,int>> ma[NP1];
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int j=0;j<n;j++)
		dist[j]=inf;
	for(int j=0;j<m;j++)
		cin>>b[j]>>p[j];
	for(int j=0;j<m;j++)
	{
		int po=b[j]+p[j];
		int le=1;
		while(po<n)
		{
			ma[b[j]].push_back({le,po});
			po+=p[j];
			le++;
		}
		po=b[j]-p[j];
		le=1;
		while(po>=0)
		{
			ma[b[j]].push_back({le,po});
			po-=p[j];
			le++;
		}
	}
	set<pair<int,int>> dp;
	dp.insert({0,b[0]});
	dist[b[0]]=0;
	while(dp.size())
	{
		auto f=*begin(dp);
		if(f.second==b[1])
		{
			cout<<f.first<<endl;
			break;
		}
		dp.erase(begin(dp));
		for(auto [ln,vp]:ma[f.second])
		{
			if(dist[vp]>(f.first+ln))
			{
				dp.erase({dist[vp],vp});
				dist[vp]=f.first+ln;
				dp.insert({dist[vp],vp});
			}
		}
	}
	if(dist[b[1]]==inf)
		cout<<-1<<'\n';
	return 0;
}

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