This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
using namespace std;
const int maxn = 210;
int ans[2001];
vector<int> qwe[2001];
vector<pair<int,int> > v;
priority_queue<pair<int,int> > q;
int n,m;
void solve(int start){
ans[start] = 0;
q.push({0,start});
while(q.size()){
//stop;
int now = q.top().second;
int dist = -q.top().first;
//cerr << now << endl;
q.pop();
if(dist > ans[now])continue;
//cout << now << ' ' << ans[now] << endl;
for(int i(0); i < qwe[now].size();i++){
int w = qwe[now][i];
int p = qwe[now][i];
int cnt = 1;
while(now+p < n){
if(ans[now+p] > ans[now]+cnt){
ans[now+p] = ans[now]+cnt;
q.push({-ans[now+p],now+p});
}
cnt++;
p+=w;
}
p = -w;
cnt = 1;
while(now+p >= 0){
if(ans[now+p] > ans[now]+cnt){
ans[now+p] = ans[now]+cnt;
q.push({-ans[now+p],now+p});
}
cnt++;
p-=w;
}
}
}
}
main(){
ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i(0);i<=n;i++)ans[i] = 1e9;
int need;
for(int i(0); i < m;i++){
int b,p; cin >> b >> p;
v.push_back({b,p});
qwe[b].push_back(p);
if(i==1)need = b;
}
solve(v[0].first);
if(ans[need] == 1e9)cout << -1;
else cout << ans[need];
}
/*
5 3
0 2
1 1
4 1
*/
Compilation message (stderr)
skyscraper.cpp: In function 'void solve(int)':
skyscraper.cpp:27:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < qwe[now].size();i++){
~~^~~~~~~~~~~~~~~~~
skyscraper.cpp: At global scope:
skyscraper.cpp:53:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:65:16: warning: 'need' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(ans[need] == 1e9)cout << -1;
~~~~~~~~^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |