제출 #60590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60590		Flugan42	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1076 ms	33716 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9223372036854775807
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)

ll n,m;
vi b,p,vis,_;
vector<vi> dog;

int main(){
  cin >> n >> m; b.assign(m,0); p.assign(m,0);
  rep(i,0,m) cin >> b[i] >> p[i];
  dog.assign(n,_);
  rep(i,0,m) dog[b[i]].push_back(i);
  vis.assign(n,0);
  priority_queue<ii> pq;
  pq.push(make_pair(0,b[0]));
  while (!pq.empty()){
    ll dist = -pq.top().first, i = pq.top().second; pq.pop();
    if (i == b[1]) {
      cout << dist << endl;
      exit(0);
    }
    if (vis[i]) continue;
    vis[i] = 1;
    rep(j,0,sz(dog[i])){
      ll px = p[dog[i][j]],cur = i+px,cnt = 1;
      while (cur < n) {
        pq.push(make_pair(-dist-cnt,cur));
        cur += px; cnt++;
      }
      cur = i-px, cnt = 1;
      while (cur >= 0){
        pq.push(make_pair(-dist-cnt,cur));
        cur -= px; cnt++;
      }
    }
  }
  cout << -1 << endl;
}

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