oj.uz

Submission #961860

# Submission time Handle Problem Language Result Execution time Memory
961860 2024-04-12T15:00:16 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
57 / 100
 432 ms 262144 KB 
#include<bits/stdc++.h>

using namespace std;

#ifdef sus
const int N=100, S=3;
#else
const int N=3e4+10, S=100;
#endif
int n, m, b[N], p[N], heavy[N];
int f[N][S+10];
vector<pair<pair<int, int>, int>> g[N][S+10];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> m;
   for (int i=1; i<=m; ++i) cin >> b[i] >> p[i], heavy[i]=p[i]>=S, ++b[i];
   for (int i=1; i<=m; ++i) if (heavy[i]){
      for (int l=b[i]-p[i], r=b[i]+p[i], cnt=1; l>=1 || r<=n; l-=p[i], r+=p[i], ++cnt){
         if (l>=1) g[b[i]][S].push_back({{l, S}, cnt});
         if (r<=n) g[b[i]][S].push_back({{r, S}, cnt});
      }
      for (int j=1; j<S; ++j) g[b[i]][j].push_back({{b[i], S}, 0});
   }
   for (int i=1; i<=m; ++i) if (!heavy[i]){
      for (int j=1; j<=S; ++j) if (j!=p[i]) g[b[i]][j].push_back({{b[i], p[i]}, 0});
   }
   for (int i=1; i<=n; ++i) for (int j=1; j<S; ++j){
      if (i-j>=1) g[i][j].push_back({{i-j, j}, 1});
      if (i+j<=n) g[i][j].push_back({{i+j, j}, 1});
   }
   priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
   memset(f, 0x3f, sizeof f);
   pq.push({f[b[1]][min(S, p[1])]=0, {b[1], min(S, p[1])}});
   while (pq.size()){
      auto u=pq.top().second;
      int d=pq.top().first;
      pq.pop();
      if (f[u.first][u.second]!=d) continue;
      for (auto &e:g[u.first][u.second]){
         auto v=e.first; int w=e.second;
         if (f[v.first][v.second]>d+w) pq.emplace(f[v.first][v.second]=d+w, v);
      }
   }
   int ans=*min_element(f[b[2]]+1, f[b[2]]+S+1);
   if (ans>1e9) ans=-1;
   cout << ans << '\n';
   return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 90704 KB Output is correct
2 Correct 22 ms 90812 KB Output is correct
3 Correct 21 ms 90968 KB Output is correct
4 Correct 20 ms 90716 KB Output is correct
5 Correct 20 ms 90716 KB Output is correct
6 Correct 20 ms 90844 KB Output is correct
7 Correct 22 ms 90716 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 90820 KB Output is correct
2 Correct 20 ms 90752 KB Output is correct
3 Correct 20 ms 90920 KB Output is correct
4 Correct 20 ms 90716 KB Output is correct
5 Correct 20 ms 90936 KB Output is correct
6 Correct 20 ms 90712 KB Output is correct
7 Correct 20 ms 90716 KB Output is correct
8 Correct 22 ms 90972 KB Output is correct
9 Correct 22 ms 90972 KB Output is correct
10 Correct 23 ms 91740 KB Output is correct
11 Correct 27 ms 94556 KB Output is correct
12 Correct 26 ms 93600 KB Output is correct
13 Correct 24 ms 93776 KB Output is correct
14 Correct 27 ms 94292 KB Output is correct
15 Correct 28 ms 94300 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 90920 KB Output is correct
2 Correct 20 ms 90712 KB Output is correct
3 Correct 20 ms 90716 KB Output is correct
4 Correct 20 ms 90940 KB Output is correct
5 Correct 21 ms 90860 KB Output is correct
6 Correct 19 ms 90716 KB Output is correct
7 Correct 20 ms 90840 KB Output is correct
8 Correct 20 ms 90972 KB Output is correct
9 Correct 22 ms 90972 KB Output is correct
10 Correct 23 ms 91740 KB Output is correct
11 Correct 27 ms 94556 KB Output is correct
12 Correct 25 ms 93392 KB Output is correct
13 Correct 27 ms 93784 KB Output is correct
14 Correct 26 ms 94300 KB Output is correct
15 Correct 26 ms 94300 KB Output is correct
16 Correct 24 ms 93020 KB Output is correct
17 Correct 33 ms 96832 KB Output is correct
18 Correct 36 ms 98612 KB Output is correct
19 Correct 35 ms 98412 KB Output is correct
20 Correct 47 ms 102996 KB Output is correct
21 Correct 28 ms 94296 KB Output is correct
22 Correct 34 ms 98140 KB Output is correct
23 Correct 35 ms 98232 KB Output is correct
24 Correct 42 ms 101208 KB Output is correct
25 Correct 45 ms 101712 KB Output is correct
26 Correct 37 ms 99836 KB Output is correct
27 Correct 38 ms 99620 KB Output is correct
28 Correct 50 ms 103120 KB Output is correct
29 Correct 49 ms 98252 KB Output is correct
30 Correct 37 ms 97472 KB Output is correct
31 Correct 42 ms 98132 KB Output is correct
32 Correct 45 ms 97744 KB Output is correct
33 Correct 56 ms 100228 KB Output is correct
34 Correct 58 ms 100304 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 90716 KB Output is correct
2 Correct 20 ms 90716 KB Output is correct
3 Correct 20 ms 90712 KB Output is correct
4 Correct 20 ms 90716 KB Output is correct
5 Correct 21 ms 90972 KB Output is correct
6 Correct 22 ms 90808 KB Output is correct
7 Correct 21 ms 90972 KB Output is correct
8 Correct 20 ms 90972 KB Output is correct
9 Correct 22 ms 90972 KB Output is correct
10 Correct 22 ms 91784 KB Output is correct
11 Correct 27 ms 94492 KB Output is correct
12 Correct 24 ms 93528 KB Output is correct
13 Correct 24 ms 93784 KB Output is correct
14 Correct 27 ms 94300 KB Output is correct
15 Correct 30 ms 94420 KB Output is correct
16 Correct 27 ms 92996 KB Output is correct
17 Correct 38 ms 96592 KB Output is correct
18 Correct 34 ms 98640 KB Output is correct
19 Correct 40 ms 98576 KB Output is correct
20 Correct 48 ms 103116 KB Output is correct
21 Correct 26 ms 94332 KB Output is correct
22 Correct 36 ms 98140 KB Output is correct
23 Correct 35 ms 98140 KB Output is correct
24 Correct 42 ms 101204 KB Output is correct
25 Correct 41 ms 101724 KB Output is correct
26 Correct 37 ms 99932 KB Output is correct
27 Correct 38 ms 99672 KB Output is correct
28 Correct 54 ms 103152 KB Output is correct
29 Correct 46 ms 98068 KB Output is correct
30 Correct 36 ms 97220 KB Output is correct
31 Correct 41 ms 98140 KB Output is correct
32 Correct 42 ms 97752 KB Output is correct
33 Correct 60 ms 100316 KB Output is correct
34 Correct 59 ms 100436 KB Output is correct
35 Correct 139 ms 142676 KB Output is correct
36 Correct 47 ms 103260 KB Output is correct
37 Correct 139 ms 132688 KB Output is correct
38 Correct 169 ms 153788 KB Output is correct
39 Correct 170 ms 153424 KB Output is correct
40 Correct 166 ms 153756 KB Output is correct
41 Correct 180 ms 153680 KB Output is correct
42 Correct 86 ms 133612 KB Output is correct
43 Correct 81 ms 133496 KB Output is correct
44 Correct 90 ms 137580 KB Output is correct
45 Correct 154 ms 149484 KB Output is correct
46 Correct 145 ms 149268 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 90712 KB Output is correct
2 Correct 20 ms 90716 KB Output is correct
3 Correct 21 ms 90712 KB Output is correct
4 Correct 20 ms 90716 KB Output is correct
5 Correct 20 ms 90840 KB Output is correct
6 Correct 22 ms 90712 KB Output is correct
7 Correct 21 ms 90716 KB Output is correct
8 Correct 20 ms 90972 KB Output is correct
9 Correct 20 ms 90972 KB Output is correct
10 Correct 25 ms 91740 KB Output is correct
11 Correct 27 ms 94616 KB Output is correct
12 Correct 23 ms 93528 KB Output is correct
13 Correct 24 ms 93784 KB Output is correct
14 Correct 28 ms 94372 KB Output is correct
15 Correct 30 ms 94424 KB Output is correct
16 Correct 24 ms 92756 KB Output is correct
17 Correct 35 ms 96852 KB Output is correct
18 Correct 34 ms 98680 KB Output is correct
19 Correct 34 ms 98404 KB Output is correct
20 Correct 48 ms 102992 KB Output is correct
21 Correct 27 ms 94332 KB Output is correct
22 Correct 34 ms 98144 KB Output is correct
23 Correct 35 ms 98140 KB Output is correct
24 Correct 45 ms 101208 KB Output is correct
25 Correct 42 ms 101712 KB Output is correct
26 Correct 37 ms 99928 KB Output is correct
27 Correct 39 ms 99676 KB Output is correct
28 Correct 50 ms 103044 KB Output is correct
29 Correct 51 ms 98272 KB Output is correct
30 Correct 39 ms 97360 KB Output is correct
31 Correct 41 ms 98252 KB Output is correct
32 Correct 39 ms 97812 KB Output is correct
33 Correct 58 ms 100316 KB Output is correct
34 Correct 57 ms 100308 KB Output is correct
35 Correct 143 ms 142676 KB Output is correct
36 Correct 46 ms 103256 KB Output is correct
37 Correct 143 ms 132880 KB Output is correct
38 Correct 170 ms 153680 KB Output is correct
39 Correct 173 ms 153324 KB Output is correct
40 Correct 183 ms 153684 KB Output is correct
41 Correct 200 ms 153424 KB Output is correct
42 Correct 80 ms 133536 KB Output is correct
43 Correct 82 ms 133520 KB Output is correct
44 Correct 91 ms 137572 KB Output is correct
45 Correct 145 ms 149360 KB Output is correct
46 Correct 145 ms 149336 KB Output is correct
47 Correct 402 ms 187988 KB Output is correct
48 Correct 268 ms 217308 KB Output is correct
49 Correct 272 ms 221988 KB Output is correct
50 Correct 256 ms 216700 KB Output is correct
51 Correct 432 ms 257420 KB Output is correct
52 Correct 429 ms 258004 KB Output is correct
53 Correct 365 ms 254436 KB Output is correct
54 Correct 206 ms 183896 KB Output is correct
55 Correct 210 ms 183780 KB Output is correct
56 Runtime error 384 ms 262144 KB Execution killed with signal 9
57 Halted 0 ms 0 KB -