Submission #961863

#	Time	Username	Problem	Language	Result	Execution time	Memory
961863		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	739 ms	243780 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;

#ifdef sus
const int N=100, S=3;
#else
const int N=3e4+10, S=80;
#endif
int n, m, b[N], p[N], heavy[N];
int f[N][S+1];
vector<pair<pair<int, int>, int>> g[N][S+1];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i) cin >> b[i] >> p[i], heavy[i]=p[i]>=S, ++b[i];
   for (int i=1; i<=m; ++i) if (heavy[i]){
      for (int l=b[i]-p[i], r=b[i]+p[i], cnt=1; l>=1 || r<=n; l-=p[i], r+=p[i], ++cnt){
         if (l>=1) g[b[i]][S].push_back({{l, S}, cnt});
         if (r<=n) g[b[i]][S].push_back({{r, S}, cnt});
      }
      for (int j=1; j<S; ++j) g[b[i]][j].push_back({{b[i], S}, 0});
   }
   for (int i=1; i<=m; ++i) if (!heavy[i]){
      for (int j=1; j<=S; ++j) if (j!=p[i]) g[b[i]][j].push_back({{b[i], p[i]}, 0});
   }
   for (int i=1; i<=n; ++i) for (int j=1; j<S; ++j){
      if (i-j>=1) g[i][j].push_back({{i-j, j}, 1});
      if (i+j<=n) g[i][j].push_back({{i+j, j}, 1});
   }
   priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
   memset(f, 0x3f, sizeof f);
   pq.push({f[b[1]][min(S, p[1])]=0, {b[1], min(S, p[1])}});
   while (pq.size()){
      auto u=pq.top().second;
      int d=pq.top().first;
      pq.pop();
      if (f[u.first][u.second]!=d) continue;
      for (auto &e:g[u.first][u.second]){
         auto v=e.first; int w=e.second;
         if (f[v.first][v.second]>d+w) pq.emplace(f[v.first][v.second]=d+w, v);
      }
   }
   int ans=*min_element(f[b[2]]+1, f[b[2]]+S+1);
   if (ans>1e9) ans=-1;
   cout << ans << '\n';
   return 0;
}

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