Submission #549250

#TimeUsernameProblemLanguageResultExecution timeMemory
549250CyberSleeperJakarta Skyscrapers (APIO15_skyscraper)C++14
0 / 100
1 ms1036 KiB
#include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define debug(x) cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl #define all(x) x.begin(), x.end() #define fi first #define se second #define mp make_pair #define pb push_back #define ll long long #define ull unsigned long long #define pll pair<ll, ll> #define pii pair<ll, ll> #define ld long double #define nl endl #define tb '\t' #define sp ' ' #define sqr(x) (x)*(x) using namespace std; const ll MX=30002, MOD=1000000007, BLOCK=327, INF=2e9+7, LG=62; const ll INFF=1000000000000000007; const ld ERR=1e-6, pi=3.14159265358979323846; int N, M, vis[MX]; vector<int> doge[MX]; int main(){ fastio; cin >> N >> M; for(int i=0; i<=N; i++) vis[i]=INF; for(int i=1, B, P; i<=M; i++){ cin >> B >> P; doge[B].pb(P); } priority_queue<pii, vector<pii>, greater<pii>> PQ; PQ.push({0, 0}); while(PQ.size()){ int cost=PQ.top().fi, idx=PQ.top().se; PQ.pop(); if(vis[idx]<cost) continue; for(int i:doge[idx]){ for(int j=1, jj; idx+i*j<=N; j++){ jj=idx+i*j; if(vis[jj]>cost+j){ vis[jj]=cost+j; PQ.push({cost+j, jj}); } } for(int j=1, jj; idx-i*j>0; j++){ jj=idx-i*j; if(vis[jj]>cost+j){ vis[jj]=cost+j; PQ.push({cost+j, jj}); } } } } if(vis[1]==INF) cout << "-1\n"; else cout << vis[1] << nl; }
#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...