제출 #393034

#제출 시각아이디문제언어결과실행 시간메모리
393034giorgikobJakarta Skyscrapers (APIO15_skyscraper)C++14
57 / 100
1088 ms17916 KiB
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; const int N = 3e4+5, mod = 1e9+7, S = 500; int n,m; int sq,pos,power; int cnt,st,f; int D[N],fix[N]; vector<pair<int,int>>gr[N]; vector<int>on_pos[N]; bool is[N][S]; int Pos[N]; inline void test_case(){ cin >> n >> m; sq = sqrt(n); cnt = n; for(int i = 1; i <= m; i++){ cin >> pos >> power; pos++; on_pos[pos].pb(power); if(power <= sq) is[pos][power] = 1; Pos[i] = pos; } for(int i = 1; i <= cnt; i++) D[i] = 1e9; priority_queue<pair<int,int>>q; q.push({0,Pos[1]}); D[Pos[1]] = 0; while(q.size()){ auto p = q.top(); q.pop(); int x = p.ss; int dist = -p.ff; if(fix[x] == 1) continue; fix[x] = 1; for(auto power : on_pos[x]){ for(int to = x+power; to <= n; to += power){ int new_dist = dist + (to-x)/power; if(new_dist < D[to]){ D[to] = new_dist; q.push({-D[to],to}); } if(power <= sq && is[to][power]) break; } for(int to = x-power; to >= 1; to -= power){ int new_dist = dist + abs(to-x)/power; if(new_dist < D[to]){ D[to] = new_dist; q.push({-D[to],to}); } if(power <= sq && is[to][power]) break; } } } if(D[Pos[2]] == 1e9) D[Pos[2]] = -1; cout << D[Pos[2]] << endl; } main(){ ios::sync_with_stdio(0); int T = 1; //cin >> T; while(T--){ test_case(); } }

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp:70:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 |  main(){
      |       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...