Submission #787947

#	Time	Username	Problem	Language	Result	Execution time	Memory
787947		devariaota	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	614 ms	6088 KiB

skyscraper

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define keish                             ios_base::sync_with_stdio(0);       cin.tie(0); cout.tie(0)
      
using namespace std;
const int mod = 1e9 + 7;

int n, m, b, p, st, ed;

signed main(){
      keish;
      cin >> n >> m;
      vector<vector<int>> e(n);
      for(int i = 0; i < m; i++){
            cin >> b >> p;
            e[b].push_back(p);
            if(i == 0) st = b;
            if(i == 1) ed = b;
      }

      vector<bool> vis(n);
      vector<int> dis(n, 1e18);
      priority_queue<pair<int, int>> pq; 

      dis[st] = 0;
      pq.push({0, st});
      
      while(!pq.empty()){
            auto [w, u] = pq.top(); pq.pop();
            w *= -1;
            if(dis[u] < w) continue;

            if(u == ed){
                  cout << dis[u] << '\n';
                  return 0;
            }
            
            if(!vis[u]){
                  vis[u] = 1;

                  for(auto p : e[u]){
                        for(int i = 1; u + i * p < n; i++){
                              int v = u + i * p;
                              if(w + i < dis[v]){
                                    dis[v] = w + i;
                                    pq.push({-dis[v], v});
                              }
                        }

                        for(int i = 1; u - i * p >= 0; i++){
                              int v = u - i * p;
                              if(w + i < dis[v]){
                                    dis[v] = w + i;
                                    pq.push({-dis[v], v});
                              }
                        }
                  }
            }
      }

      cout << -1 << '\n';
}          

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