Submission #903855

#	Time	Username	Problem	Language	Result	Execution time	Memory
903855		oblantis	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	602 ms	4056 KiB

skyscraper

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 30000;
void solve() {
    int n, m;
    cin >> n >> m;
    int a[m], b[m];
    vt<int> it[n];
    int dp[n];
    for(int i = 0; i < n; i++)dp[i] = inf;
    for(int i = 0; i < m; i++){
		cin >> a[i] >> b[i];
		it[a[i]].pb(i);
	}
	priority_queue<pii, vt<pii>, greater<pii>> pq;
	pq.push({0, a[0]});
	dp[a[0]] = 0;
	while(!pq.empty()){
		pii nw = pq.top();
		pq.pop();
		if(dp[nw.ss] != nw.ff)continue;
		for(auto i : it[nw.ss]){
			int x = b[i];
			for(int j = nw.ss - x, cnt = 1; j >= 0; cnt++, j -= x){
				if(dp[j] > nw.ff + cnt){
					dp[j] = nw.ff + cnt;
					pq.push({dp[j], j});
				}
			}
			for(int j = nw.ss + x, cnt = 1; j < n; cnt++, j += x){
				if(dp[j] > nw.ff + cnt){
					dp[j] = nw.ff + cnt;
					pq.push({dp[j], j});
				}
			}
		}
	}
	if(dp[a[1]] == inf)cout << -1;
	else cout << dp[a[1]];
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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