제출 #916065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916065		Aiperiii	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	1 ms	2396 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
const int N=2e3+5,M=3e4+5;
int g[N][M];
signed 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++){
      int b,p;
      cin>>b>>p;
      int x=b+p;
      int cnt=1;
      while(x<n){
         g[b][x]=cnt;
         x+=p;
         cnt++;
      }
      x=b-p;
      cnt=1;
      while(x>=0){
         g[b][x]=cnt;
         x-=p;
         cnt++;
      }
   }
   set <pair <int,int> > st;
   vector <int> d(n+1,1e18);
   st.insert({0,0});
   d[0]=0;
   while(!st.empty()){
      int v=st.begin()->second;
      st.erase(st.begin());
      for(int i=0;i<=n;i++){
         if(g[v][i]==0)continue;
         if(d[i]>d[v]+g[v][i]){
            st.erase({d[i],i});
            d[i]=d[v]+g[v][i];
            st.insert({d[i],i});
         }
      }
   }
   if(d[1]==1e18)d[1]=-1;
   cout<<d[1]<<"\n";
}

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