oj.uz

Submission #961855

# Submission time Handle Problem Language Result Execution time Memory
961855 2024-04-12T14:56:45 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++14
22 / 100
 30 ms 94680 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 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 20 ms 90712 KB Output is correct
2 Correct 20 ms 90716 KB Output is correct
3 Correct 20 ms 90900 KB Output is correct
4 Correct 21 ms 90932 KB Output is correct
5 Correct 20 ms 90900 KB Output is correct
6 Correct 21 ms 90724 KB Output is correct
7 Correct 19 ms 90716 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 90936 KB Output is correct
2 Correct 20 ms 90716 KB Output is correct
3 Correct 21 ms 90828 KB Output is correct
4 Correct 20 ms 90712 KB Output is correct
5 Correct 20 ms 90948 KB Output is correct
6 Correct 21 ms 90720 KB Output is correct
7 Correct 21 ms 90716 KB Output is correct
8 Correct 20 ms 91008 KB Output is correct
9 Correct 21 ms 90972 KB Output is correct
10 Correct 23 ms 91736 KB Output is correct
11 Correct 27 ms 94556 KB Output is correct
12 Correct 24 ms 93532 KB Output is correct
13 Correct 24 ms 93788 KB Output is correct
14 Correct 27 ms 94296 KB Output is correct
15 Correct 30 ms 94288 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 90944 KB Output is correct
2 Correct 20 ms 90840 KB Output is correct
3 Correct 23 ms 90716 KB Output is correct
4 Correct 22 ms 90716 KB Output is correct
5 Correct 21 ms 90716 KB Output is correct
6 Correct 20 ms 90716 KB Output is correct
7 Correct 20 ms 90712 KB Output is correct
8 Correct 20 ms 90972 KB Output is correct
9 Correct 21 ms 91088 KB Output is correct
10 Correct 23 ms 91740 KB Output is correct
11 Correct 27 ms 94680 KB Output is correct
12 Correct 27 ms 93524 KB Output is correct
13 Correct 24 ms 93788 KB Output is correct
14 Correct 27 ms 94296 KB Output is correct
15 Correct 28 ms 94300 KB Output is correct
16 Correct 23 ms 92248 KB Output is correct
17 Incorrect 29 ms 94044 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.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 20 ms 90716 KB Output is correct
4 Correct 20 ms 90716 KB Output is correct
5 Correct 21 ms 90716 KB Output is correct
6 Correct 20 ms 90716 KB Output is correct
7 Correct 20 ms 90936 KB Output is correct
8 Correct 20 ms 90968 KB Output is correct
9 Correct 22 ms 90972 KB Output is correct
10 Correct 22 ms 91740 KB Output is correct
11 Correct 28 ms 94556 KB Output is correct
12 Correct 24 ms 93520 KB Output is correct
13 Correct 25 ms 93788 KB Output is correct
14 Correct 27 ms 94300 KB Output is correct
15 Correct 27 ms 94296 KB Output is correct
16 Correct 23 ms 92248 KB Output is correct
17 Incorrect 30 ms 94088 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 90712 KB Output is correct
2 Correct 20 ms 90748 KB Output is correct
3 Correct 20 ms 90716 KB Output is correct
4 Correct 20 ms 90944 KB Output is correct
5 Correct 20 ms 90940 KB Output is correct
6 Correct 21 ms 90712 KB Output is correct
7 Correct 21 ms 90712 KB Output is correct
8 Correct 20 ms 90968 KB Output is correct
9 Correct 20 ms 90972 KB Output is correct
10 Correct 23 ms 91736 KB Output is correct
11 Correct 27 ms 94556 KB Output is correct
12 Correct 23 ms 93472 KB Output is correct
13 Correct 23 ms 93788 KB Output is correct
14 Correct 28 ms 94396 KB Output is correct
15 Correct 26 ms 94452 KB Output is correct
16 Correct 23 ms 92252 KB Output is correct
17 Incorrect 30 ms 94032 KB Output isn't correct
18 Halted 0 ms 0 KB -