Submission #45210

#	Time	Username	Problem	Language	Result	Execution time	Memory
45210		ckodser	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	140 ms	142276 KiB

skyscraper

#include<bits/stdc++.h>

#define ll	int 
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=3e4+10;
const ll mod=1e9+7;
const ll inf=1e9+500;
const ll rad=100;
const ll maxm=maxn*(rad)*2+50;

ll b[maxn];
ll p[maxn];
vector<ll> vec[maxn];

vector<pair<ll,short> > ger[maxm];
ll h[maxm];


int main(){

	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>b[i]>>p[i];
		vec[b[i]].pb(i);
	}
	for(ll i=0;i<n;i++){
		for(auto v:vec[i]){
			ger[i+m].pb(mp(v,0));
		}
	}	


	for(ll j=1;j<rad;j++){
		for(ll i=0;i<n;i++){
			ger[m+j*n+i].pb(mp(i+m,0));
			if(i>=j){
				ger[m+j*n+i].pb(mp(m+j*n+i-j,1));
			}
		}
	}
	for(ll j=1;j<rad;j++){
		for(ll i=0;i<n;i++){
			ll v=m+rad*n+(j-1)*n+i;
			ger[v].pb(mp(i+m,0));
			if(i+j<n){
				ger[v].pb(mp(v+j,1));
			}
		}
	}
	for(ll i=0;i<m;i++){
		if(p[i]<rad){
			ll v=b[i];
			ger[i].pb(mp(m+n*p[i]+v,0));
			ger[i].pb(mp(m+rad*n+(p[i]-1)*n+v,0));
		}
	}



	for(ll i=0;i<m;i++){
		if(p[i]>=rad){
			for(ll j=b[i];j<n;j+=p[i]){
				ger[i].pb(mp(j+m,(j-b[i])/p[i]));
			}
			for(ll j=b[i]-p[i];j>=0;j-=p[i]){
				ger[i].pb(mp(j+m,(b[i]-j)/p[i]));
			}	
		}		
	}




	priority_queue<pii> st;
	st.push(mp(-1,0));
	while(st.size()){
		ll v=(st.top()).S;
		ll w=(st.top()).F;
		st.pop();
		if(h[v]==0){
			h[v]=-w;
			for(auto e:ger[v]){
				st.push(mp(e.S-w,e.F));
			}
		}
	}
	if(h[1]==0){
		cout<<-1;
	}else{
		cout<<h[1]-1;
	}
}

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