oj.uz

Submission #961862

# Submission time Handle Problem Language Result Execution time Memory
961862 2024-04-12T15:04:05 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
36 / 100
 206 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=200;
#endif
int n, m, b[N], p[N], heavy[N];
int f[N][S+1];
vector<pair<pair<int, int>, int>> g[N][S+1];

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 47 ms 165588 KB Output is correct
2 Correct 39 ms 165712 KB Output is correct
3 Correct 36 ms 165720 KB Output is correct
4 Correct 36 ms 165716 KB Output is correct
5 Correct 37 ms 165708 KB Output is correct
6 Correct 37 ms 165716 KB Output is correct
7 Correct 37 ms 165752 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 165720 KB Output is correct
2 Correct 37 ms 165724 KB Output is correct
3 Correct 37 ms 165712 KB Output is correct
4 Correct 37 ms 165720 KB Output is correct
5 Correct 37 ms 165496 KB Output is correct
6 Correct 36 ms 165716 KB Output is correct
7 Correct 38 ms 165720 KB Output is correct
8 Correct 36 ms 165708 KB Output is correct
9 Correct 37 ms 165948 KB Output is correct
10 Correct 48 ms 167248 KB Output is correct
11 Correct 49 ms 172880 KB Output is correct
12 Correct 44 ms 170588 KB Output is correct
13 Correct 43 ms 171292 KB Output is correct
14 Correct 51 ms 172280 KB Output is correct
15 Correct 51 ms 172508 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 165720 KB Output is correct
2 Correct 36 ms 165716 KB Output is correct
3 Correct 37 ms 165736 KB Output is correct
4 Correct 36 ms 165716 KB Output is correct
5 Correct 36 ms 165712 KB Output is correct
6 Correct 36 ms 165724 KB Output is correct
7 Correct 37 ms 165716 KB Output is correct
8 Correct 37 ms 165724 KB Output is correct
9 Correct 38 ms 165980 KB Output is correct
10 Correct 43 ms 167248 KB Output is correct
11 Correct 54 ms 173136 KB Output is correct
12 Correct 48 ms 170576 KB Output is correct
13 Correct 43 ms 171088 KB Output is correct
14 Correct 47 ms 172512 KB Output is correct
15 Correct 49 ms 172368 KB Output is correct
16 Correct 44 ms 169420 KB Output is correct
17 Correct 61 ms 177232 KB Output is correct
18 Correct 67 ms 181132 KB Output is correct
19 Correct 65 ms 180840 KB Output is correct
20 Correct 83 ms 189416 KB Output is correct
21 Correct 48 ms 172204 KB Output is correct
22 Correct 65 ms 180048 KB Output is correct
23 Correct 64 ms 180132 KB Output is correct
24 Correct 78 ms 185920 KB Output is correct
25 Correct 76 ms 186964 KB Output is correct
26 Correct 70 ms 183908 KB Output is correct
27 Correct 73 ms 183380 KB Output is correct
28 Correct 98 ms 189504 KB Output is correct
29 Correct 77 ms 180300 KB Output is correct
30 Correct 70 ms 178832 KB Output is correct
31 Correct 73 ms 180304 KB Output is correct
32 Correct 73 ms 179556 KB Output is correct
33 Correct 92 ms 184436 KB Output is correct
34 Correct 96 ms 184284 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 165724 KB Output is correct
2 Correct 38 ms 165720 KB Output is correct
3 Correct 42 ms 165720 KB Output is correct
4 Correct 38 ms 165724 KB Output is correct
5 Correct 36 ms 165472 KB Output is correct
6 Correct 37 ms 165716 KB Output is correct
7 Correct 37 ms 165712 KB Output is correct
8 Correct 36 ms 165968 KB Output is correct
9 Correct 40 ms 165832 KB Output is correct
10 Correct 40 ms 167248 KB Output is correct
11 Correct 49 ms 173000 KB Output is correct
12 Correct 41 ms 170580 KB Output is correct
13 Correct 43 ms 171088 KB Output is correct
14 Correct 50 ms 172316 KB Output is correct
15 Correct 52 ms 172460 KB Output is correct
16 Correct 44 ms 169296 KB Output is correct
17 Correct 62 ms 176972 KB Output is correct
18 Correct 66 ms 181076 KB Output is correct
19 Correct 68 ms 180796 KB Output is correct
20 Correct 84 ms 189392 KB Output is correct
21 Correct 47 ms 172208 KB Output is correct
22 Correct 64 ms 180272 KB Output is correct
23 Correct 65 ms 180132 KB Output is correct
24 Correct 78 ms 185940 KB Output is correct
25 Correct 76 ms 187036 KB Output is correct
26 Correct 71 ms 183596 KB Output is correct
27 Correct 73 ms 183296 KB Output is correct
28 Correct 91 ms 189268 KB Output is correct
29 Correct 77 ms 180396 KB Output is correct
30 Correct 72 ms 178836 KB Output is correct
31 Correct 73 ms 180472 KB Output is correct
32 Correct 70 ms 179764 KB Output is correct
33 Correct 95 ms 184432 KB Output is correct
34 Correct 102 ms 184432 KB Output is correct
35 Runtime error 206 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 165712 KB Output is correct
2 Correct 36 ms 165684 KB Output is correct
3 Correct 36 ms 165744 KB Output is correct
4 Correct 37 ms 165588 KB Output is correct
5 Correct 36 ms 165724 KB Output is correct
6 Correct 36 ms 165720 KB Output is correct
7 Correct 36 ms 165724 KB Output is correct
8 Correct 36 ms 165716 KB Output is correct
9 Correct 38 ms 165988 KB Output is correct
10 Correct 39 ms 167264 KB Output is correct
11 Correct 49 ms 172880 KB Output is correct
12 Correct 42 ms 170824 KB Output is correct
13 Correct 45 ms 171244 KB Output is correct
14 Correct 46 ms 172368 KB Output is correct
15 Correct 46 ms 172372 KB Output is correct
16 Correct 43 ms 169304 KB Output is correct
17 Correct 63 ms 176952 KB Output is correct
18 Correct 64 ms 181160 KB Output is correct
19 Correct 65 ms 180804 KB Output is correct
20 Correct 84 ms 189264 KB Output is correct
21 Correct 47 ms 172064 KB Output is correct
22 Correct 64 ms 180056 KB Output is correct
23 Correct 64 ms 180048 KB Output is correct
24 Correct 77 ms 185748 KB Output is correct
25 Correct 75 ms 187044 KB Output is correct
26 Correct 72 ms 183524 KB Output is correct
27 Correct 74 ms 183472 KB Output is correct
28 Correct 89 ms 189260 KB Output is correct
29 Correct 78 ms 180432 KB Output is correct
30 Correct 71 ms 178776 KB Output is correct
31 Correct 72 ms 180320 KB Output is correct
32 Correct 73 ms 179776 KB Output is correct
33 Correct 92 ms 184392 KB Output is correct
34 Correct 103 ms 184264 KB Output is correct
35 Runtime error 196 ms 262144 KB Execution killed with signal 9
36 Halted 0 ms 0 KB -