Submission #1288161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288161		lambd47	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	550 ms	327680 KiB

skyscraper

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;

#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())





void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> pos(m);
	vector<int> pulo(m);
	L(i,0,m-1)cin>>pos[i]>>pulo[i];
	vector<vector<int>> amigos(n);
	L(i,0,m-1){
		amigos[pos[i]].push_back(i);
	}	

	const int MOD=1e9+7;
	vector<int> dp(m,MOD);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	for(auto a:amigos[pos[0]]){
		dp[a]=0;
		pq.push({0,a});
	}
	amigos[pos[0]].clear();
	while(!pq.empty()){//posso deletar os carinhas do amigo se tiver ruim
		auto [d,v]=pq.top();
		pq.pop();
		
		if(v<0){
		    v++;
		    v=-v;
		    while(!amigos[v].empty()){
		        auto a=amigos[v].back();
		        amigos[v].pop_back();
		        dp[a]=d;
		        pq.push({dp[a],a});
		    }
		    continue;
		}
		
		if(d!=dp[v])continue;
		if(v==1)break;
		
		for(int i=1;pulo[v]*i+pos[v]<n;i++){
			int casa=i*pulo[v]+pos[v];
			if(!amigos[casa].empty())pq.push({dp[v]+i,-casa-1});
			/*for(auto a:amigos[casa]){
				if(dp[a]>dp[v]+i){
					dp[a]=dp[v]+i;
					pq.push({dp[a],a});
				}
			}*/
		}
		for(int i=1;pos[v]-pulo[v]*i>=0;i++){
			int casa=pos[v]-i*pulo[v];
			if(!amigos[casa].empty())pq.push({dp[v]+i,-casa-1});
			/*
			for(auto a:amigos[casa]){
				if(dp[a]>dp[v]+i){
					dp[a]=dp[v]+i;
					pq.push({dp[a],a});
				}
			}*/
		}
	}	
//	L(i,0,m-1)cout<<dp[i]<<" ";
	cout<<((dp[1]==MOD)?-1:dp[1]);
	
	
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();
}

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