# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

1041290 | 2024-08-01T20:16:41 Z | Math4Life2020 | Jakarta Skyscrapers (APIO15_skyscraper) | C++17 | 1000 ms | 2988 KB |

// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll,ll>; int main() { ll N,M; cin >> N >> M; ll K = floor(sqrt(N+0.001)); ll B[M],P[M]; bool found[N]; //ll val[M]; ll val[N]; vector<pii> doges[N]; for (ll i=0;i<M;i++) { //val[i]=1e18; cin >> B[i] >> P[i]; doges[B[i]].push_back({i,P[i]}); } for (ll i=0;i<N;i++) { val[i]=1e18; found[i]=0; } val[B[0]]=0; while(1) { ll mv = 1e17; ll ctr = -1; for (ll i=0;i<N;i++) { if (val[i]<mv && !found[i]) { mv = val[i]; ctr = i; } } if (ctr==-1) { cout << "-1"; exit(0); } else if (ctr==B[1]) { cout << val[B[1]]; exit(0); } else { for (pii x0: doges[ctr]) { ll i = x0.first; for (ll t=(-(B[i]/P[i]+2));t<(((N-B[i])/P[i])+2);t++) { if ((B[i]+t*P[i])>=0 && (B[i]+t*P[i])<N) { val[(B[i]+t*P[i])]=min(val[(B[i]+t*P[i])],mv+(ll)abs(t)); } } } } found[ctr]=1; } }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 1 ms | 348 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 348 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 436 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 1 ms | 348 KB | Output is correct |

12 | Correct | 1 ms | 348 KB | Output is correct |

13 | Correct | 1 ms | 348 KB | Output is correct |

14 | Correct | 1 ms | 348 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 344 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 1 ms | 348 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 1 ms | 348 KB | Output is correct |

14 | Correct | 1 ms | 348 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

16 | Correct | 0 ms | 348 KB | Output is correct |

17 | Correct | 1 ms | 348 KB | Output is correct |

18 | Correct | 1 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 6 ms | 412 KB | Output is correct |

21 | Correct | 1 ms | 344 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 2 ms | 348 KB | Output is correct |

24 | Correct | 3 ms | 348 KB | Output is correct |

25 | Correct | 1 ms | 348 KB | Output is correct |

26 | Correct | 2 ms | 604 KB | Output is correct |

27 | Correct | 3 ms | 604 KB | Output is correct |

28 | Correct | 3 ms | 616 KB | Output is correct |

29 | Correct | 3 ms | 604 KB | Output is correct |

30 | Correct | 2 ms | 500 KB | Output is correct |

31 | Correct | 3 ms | 524 KB | Output is correct |

32 | Correct | 3 ms | 348 KB | Output is correct |

33 | Correct | 3 ms | 348 KB | Output is correct |

34 | Correct | 3 ms | 592 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 436 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 432 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 436 KB | Output is correct |

11 | Correct | 0 ms | 528 KB | Output is correct |

12 | Correct | 1 ms | 348 KB | Output is correct |

13 | Correct | 1 ms | 348 KB | Output is correct |

14 | Correct | 1 ms | 348 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

16 | Correct | 1 ms | 348 KB | Output is correct |

17 | Correct | 1 ms | 348 KB | Output is correct |

18 | Correct | 0 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 7 ms | 604 KB | Output is correct |

21 | Correct | 1 ms | 348 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 2 ms | 348 KB | Output is correct |

24 | Correct | 3 ms | 348 KB | Output is correct |

25 | Correct | 1 ms | 348 KB | Output is correct |

26 | Correct | 2 ms | 608 KB | Output is correct |

27 | Correct | 3 ms | 604 KB | Output is correct |

28 | Correct | 4 ms | 600 KB | Output is correct |

29 | Correct | 3 ms | 348 KB | Output is correct |

30 | Correct | 2 ms | 348 KB | Output is correct |

31 | Correct | 3 ms | 348 KB | Output is correct |

32 | Correct | 3 ms | 348 KB | Output is correct |

33 | Correct | 3 ms | 344 KB | Output is correct |

34 | Correct | 3 ms | 348 KB | Output is correct |

35 | Correct | 8 ms | 1804 KB | Output is correct |

36 | Correct | 2 ms | 604 KB | Output is correct |

37 | Correct | 7 ms | 1372 KB | Output is correct |

38 | Correct | 9 ms | 1884 KB | Output is correct |

39 | Correct | 8 ms | 1884 KB | Output is correct |

40 | Correct | 10 ms | 1884 KB | Output is correct |

41 | Correct | 9 ms | 1880 KB | Output is correct |

42 | Correct | 8 ms | 1752 KB | Output is correct |

43 | Correct | 8 ms | 1760 KB | Output is correct |

44 | Correct | 76 ms | 1752 KB | Output is correct |

45 | Correct | 16 ms | 1936 KB | Output is correct |

46 | Correct | 11 ms | 1884 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 344 KB | Output is correct |

2 | Correct | 0 ms | 348 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 432 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 0 ms | 348 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 1 ms | 348 KB | Output is correct |

14 | Correct | 0 ms | 348 KB | Output is correct |

15 | Correct | 1 ms | 348 KB | Output is correct |

16 | Correct | 1 ms | 348 KB | Output is correct |

17 | Correct | 1 ms | 348 KB | Output is correct |

18 | Correct | 1 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 6 ms | 592 KB | Output is correct |

21 | Correct | 0 ms | 348 KB | Output is correct |

22 | Correct | 1 ms | 348 KB | Output is correct |

23 | Correct | 2 ms | 348 KB | Output is correct |

24 | Correct | 3 ms | 348 KB | Output is correct |

25 | Correct | 1 ms | 348 KB | Output is correct |

26 | Correct | 3 ms | 604 KB | Output is correct |

27 | Correct | 3 ms | 604 KB | Output is correct |

28 | Correct | 3 ms | 612 KB | Output is correct |

29 | Correct | 3 ms | 348 KB | Output is correct |

30 | Correct | 3 ms | 348 KB | Output is correct |

31 | Correct | 3 ms | 348 KB | Output is correct |

32 | Correct | 3 ms | 348 KB | Output is correct |

33 | Correct | 3 ms | 348 KB | Output is correct |

34 | Correct | 3 ms | 592 KB | Output is correct |

35 | Correct | 8 ms | 1728 KB | Output is correct |

36 | Correct | 2 ms | 604 KB | Output is correct |

37 | Correct | 7 ms | 1464 KB | Output is correct |

38 | Correct | 10 ms | 1880 KB | Output is correct |

39 | Correct | 8 ms | 1884 KB | Output is correct |

40 | Correct | 7 ms | 1868 KB | Output is correct |

41 | Correct | 8 ms | 1880 KB | Output is correct |

42 | Correct | 8 ms | 1784 KB | Output is correct |

43 | Correct | 9 ms | 1748 KB | Output is correct |

44 | Correct | 59 ms | 1752 KB | Output is correct |

45 | Correct | 10 ms | 1928 KB | Output is correct |

46 | Correct | 10 ms | 1792 KB | Output is correct |

47 | Correct | 50 ms | 2136 KB | Output is correct |

48 | Correct | 7 ms | 2140 KB | Output is correct |

49 | Correct | 7 ms | 2140 KB | Output is correct |

50 | Correct | 5 ms | 2140 KB | Output is correct |

51 | Execution timed out | 1054 ms | 2988 KB | Time limit exceeded |

52 | Halted | 0 ms | 0 KB | - |