Submission #1096956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096956		lmToT27	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	65 ms	5836 KiB

skyscraper

#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long

using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}

const int MAX = 3e4 + 3;
const ll MOD[] = {1000000007, 998244353};

int n, m;
int b[MAX], p[MAX];
int dp[MAX];
set <int> f[MAX];

void Solve() {
        memset(dp, 0x0f, sizeof dp);
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
                cin >> b[i] >> p[i];
                f[b[i]].insert(p[i]);
        }

        priority_queue <pair <int, int>> q;
        dp[b[0]] = 0;
        q.push({0, b[0]});
        while (q.size()) {
                auto [D, u] = q.top();
                q.pop();
                D = -D;
                if (D != dp[u]) continue;
                if (u == b[1]) return void(cout << D);
                for (auto p : f[u]) {
                        for (int v = u + p; v < n; v += p) {
                                if (dp[v] > D + (v - u) / p) {
                                        dp[v] = D + (v - u) / p;
                                        q.emplace(-dp[v], v);
                                }
                                if (f[v].count(p)) break;
                        }
                        for (int v = u - p; v >= 0; v -= p) {
                                if (dp[v] > D + (u - v) / p) {
                                        dp[v] = D + (u - v) / p;
                                        q.emplace(-dp[v], v);
                                }
                                if (f[v].count(p)) break;
                        }
                }
        }
        cout << -1;
}

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        #define TASK "TASK"
        if (fopen(TASK".INP", "r")) {
                freopen(TASK".INP", "r", stdin);
                freopen(TASK".OUT", "w", stdout);
        }
        
        /* int TEST = 1; cin >> TEST; while (TEST--) */ Solve();

        cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
        return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:72:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |                 freopen(TASK".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:73:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |                 freopen(TASK".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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