Submission #905815

#	Time	Username	Problem	Language	Result	Execution time	Memory
905815		Faisal_Saqib	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	29 ms	1036 KiB

skyscraper

#include <iostream>
#include <set>
#include <vector>
using namespace std;
const int NP=3e4+10;
const int NP1=2e3+10;
const long long inf=1e18;
long long dist[NP1];
int b[NP],p[NP];
vector<int> len[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];
		len[b[j]].push_back(p[j]);
	}
	set<pair<long long,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<<'\n';
			break;
		}
		dp.erase(begin(dp));
		for(auto lp:len[f.second])
		{
			int po=f.second+lp;
			int le=1;
			while(po<n)
			{
				if(dist[po]>f.first+le)
				{
					dp.erase({dist[po],po});
					dist[po]=f.first+le;
					dp.insert({dist[po],po});
				}
				po+=lp;
				le++;
			}
			po=f.second-lp;
			le=1;
			while(po>=0)
			{
				if(dist[po]>f.first+le)
				{
					dp.erase({dist[po],po});
					dist[po]=f.first+le;
					dp.insert({dist[po],po});
				}
				po-=lp;
				le++;
			}
		}
	}
	if(dist[b[1]]==inf)
		cout<<-1<<'\n';
	return 0;
}

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