Submission #1272915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272915		zNatsumi	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	580 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 3e4 + 5;

int n, m, f[N];
vector<int> ad[N];

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m;
  for(int i = 1; i <= m; i++){
    int u, d; cin >> u >> d;
    ad[u].push_back(d);
  }
  for(int u = 0; u < n; u++){
    sort(ad[u].begin(), ad[u].end());
    ad[u].erase(unique(ad[u].begin(), ad[u].end()), ad[u].end());
    reverse(ad[u].begin(), ad[u].end());
  }

  for(int i = 1; i < n; i++) f[i] = 1'000'000'000'000'000;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  pq.push({0, 0});

  while(pq.size()){
    auto [d, u] = pq.top(); pq.pop();

    if(d != f[u]) continue;
    if(u == 1) return cout << d, 0;

    for(auto w : ad[u]){
      for(int i = 1; u + i * w < n; i++){
        if(d + i < f[u + i * w]) pq.push({f[u + i * w] = d + i, u + i * w});
      }

      for(int i = 1; u - i * w >= 0; i++)
        if(d + i < f[u - i * w]) pq.push({f[u - i * w] = d + i, u - i * w});
    }
  }
  cout << -1 << "\n";

  return 0;
}

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