Submission #1182427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182427		boclobanchat	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	100 / 100	46 ms	10176 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=3e4+5;
const int sqr=222;
int dp[MAXN];
bool ck[MAXN][sqr+5];
vector<int> vi[MAXN];
priority_queue< ii,vector<ii>,greater<ii> > pq;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,st=0,ed=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int b,p;
		cin>>b>>p;
		if(i==1) st=b;
		if(i==2) ed=b;
		vi[b].push_back(p);
	}
	for(int i=0;i<n;i++) dp[i]=1e9;
	pq.push({dp[st]=0,st});
	while(!pq.empty())
	{
		int a=pq.top().fi,b=pq.top().se;
		pq.pop();
		if(dp[b]<a) continue;
		for(auto v:vi[b])
		{
			if(v<=sqr) ck[b][v]=true;
			int pos=b,cnt=0;
			while(pos+v<n)
			{
				pos+=v,cnt++;
				if(v<=sqr&&ck[pos][v]) break;
				if(dp[pos]>a+cnt) pq.push({dp[pos]=a+cnt,pos});
				if(v<=sqr) ck[pos][v]=true;
			}
			pos=b,cnt=0;
			while(pos-v>=0)
			{
				pos-=v,cnt++;
				if(v<=sqr&&ck[pos][v]) break;
				if(dp[pos]>a+cnt) pq.push({dp[pos]=a+cnt,pos});
				if(v<=sqr) ck[pos][v]=true;
			}
		}
	}
	if(dp[ed]==1e9) cout<<-1;
	else cout<<dp[ed];
}

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