제출 #874643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874643		Iliya_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	23 ms	860 KiB

skyscraper

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define all(x)      x.begin(),x.end()
#define pb          push_back
using namespace std;
typedef long long ll; 

#define int long long 
const int N = 2e3+7, NN = 3e4+7, inf = 1e18;
int a[N], p[N], d[N], mark[N];
vector<int> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q; 

void dij(int n){
     fill(d,d+n,inf);
     d[a[0]] = 0; 
     q.push({0,a[0]}); 
     while(q.size()){
          int v = q.top().S;
          q.pop();
          if (mark[v]) continue; 
          mark[v] = 1;
          for (int p : g[v]){
               for(int i=v; i<n; i+=p){
                    if (d[i] > d[v] + (i-v)/p){
                         d[i] = d[v] + (i-v)/p;
                         q.push({d[i],i}); 
                    }
               }
               for(int i=v; i>=0; i-=p){
                    if (d[i] > d[v] + (v-i)/p){
                         d[i] = d[v] + (v-i)/p;
                         q.push({d[i],i});
                    }
               }
          }
     }
}

int32_t main(){
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
     
     int n,m; cin >> n >> m; 
     for(int i=0; i<m; i++){
          cin >> a[i] >> p[i]; 
          g[a[i]].pb(p[i]);
     }
     dij(n); 
     cout << (d[a[1]] == inf ? -1 : d[a[1]]) << endl; 

     return 0;
}

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