제출 #1275676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275676		SinaPourkashani	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1096 ms	3072 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector <pair<ll, ll>> vp;
typedef pair<ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sll;
#define pb push_back
#define ff first
#define ss second
#define str to_string
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto i : x) cout << i << ' '; cout << '\n';
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);

const ll maxn = 3e4+5;
const ll mod = 1e9+7;
const ll inf = 1e18;

ll pw(ll a, ll b, ll M = mod) {ll ans = 1; for (; b; a = ((a * a) % M), b >>= 1) if (b & 1) ans = (ans * a) % M; return ans;}

ll n, m, b[maxn], p[maxn], dist[maxn];
vll dgs[maxn];

int main() {
    FastIO

    cin >> n >> m;

    for (ll i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        dgs[b[i]].pb(i);  
    }

    fill(dist+1, dist+m, inf);

    queue <ll> q;
    q.push(0);

    while (!q.empty()) {
        ll v = q.front();
        q.pop();

        for (ll i = b[v], d = 0; i >= 0; i -= p[v], d++) {
            for (ll u : dgs[i]) {
                if (dist[u] > dist[v] + d) {
                    dist[u] = dist[v] + d;
                    q.push(u);
                }
            }
        }

        for (ll i = b[v]+p[v], d = 1; i < n; i += p[v], d++) {
            for (ll u : dgs[i]) {
                if (dist[u] > dist[v] + d) {
                    dist[u] = dist[v] + d;
                    q.push(u);
                }
            }
        }
    }

    if (dist[1] < inf) cout << dist[1] << '\n';
    else 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