oj.uz

Submission #1110720

# Submission time Handle Problem Language Result Execution time Memory
1110720 2024-11-10T09:14:53 Z nhphuc Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 130 ms 190836 KB 
#include <bits/stdc++.h>
using namespace std;

#define iii tuple<int, int, int>

const int N = 50500;
const int block = 157;

int n, m, b[N], v[N], dp[N][block + 7], ans = -1;
bool vis[N][block + 7];
vector<int> pw[N];
vector<pair<int, int>> Q[N * block + 107];

int32_t main (){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    if (fopen("test.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= block + 1; ++j)
            dp[i][j] = -1;
    for (int i = 1; i <= m; ++i){
        cin >> b[i] >> v[i];
        pw[b[i]].push_back(v[i]);
        if (i == 1)
            Q[0].push_back({b[i], v[i]});
    }
    for (int D = 0; D < N * block; ++D){
        for (pair<int, int> it : Q[D]){
            int u = it.first;
            int t = it.second;
            if (dp[u][t] != -1)
                continue;
            if (vis[u][t])
                continue;
            vis[u][t] = true;
            dp[u][t] = D;
            if (u == b[2])
                ans = min((ans == -1 ? (int)1e16 : ans), D);
            if (t <= block){
                if (u - t >= 0 && dp[u - t][t] == -1)
                    Q[D + 1].push_back({u - t, t});
                if (u + t < n && dp[u + t][t] == -1)
                    Q[D + 1].push_back({u + t, t});
            }
            for (int X : pw[u]){
                if (X <= block){
                    if (u - X >= 0 && dp[u - X][X] == -1)
                        Q[D + 1].push_back({u - X, X});
                    if (u + X < n && dp[u + X][X] == -1)
                        Q[D + 1].push_back({u + X, X});
                } else {
                    for (int i = u - X; i >= 0; i -= X)
                        if (dp[i][block + 1] == -1)
                            Q[D + (u - i) / X].push_back({i, X});
                    for (int i = u + X; i < n; i += X)
                        if (dp[i][block + 1] == -1)
                            Q[D + (i - u) / X].push_back({i, X});
                }
            }
        }
    }
    cout << ans << "\n";
}

Compilation message

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:18:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 189256 KB Output is correct
2 Correct 111 ms 189268 KB Output is correct
3 Correct 116 ms 189256 KB Output is correct
4 Correct 115 ms 189296 KB Output is correct
5 Correct 113 ms 189256 KB Output is correct
6 Correct 112 ms 189256 KB Output is correct
7 Correct 110 ms 189416 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 189204 KB Output is correct
2 Correct 118 ms 189256 KB Output is correct
3 Correct 113 ms 189256 KB Output is correct
4 Correct 113 ms 189256 KB Output is correct
5 Correct 113 ms 189224 KB Output is correct
6 Correct 110 ms 189256 KB Output is correct
7 Correct 110 ms 189304 KB Output is correct
8 Correct 111 ms 189324 KB Output is correct
9 Correct 112 ms 189328 KB Output is correct
10 Correct 113 ms 189468 KB Output is correct
11 Correct 115 ms 189768 KB Output is correct
12 Correct 108 ms 189512 KB Output is correct
13 Correct 104 ms 189348 KB Output is correct
14 Correct 109 ms 189768 KB Output is correct
15 Correct 112 ms 189512 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 189216 KB Output is correct
2 Correct 115 ms 189264 KB Output is correct
3 Correct 111 ms 189256 KB Output is correct
4 Correct 123 ms 189416 KB Output is correct
5 Correct 116 ms 189360 KB Output is correct
6 Correct 119 ms 189256 KB Output is correct
7 Correct 129 ms 189256 KB Output is correct
8 Correct 104 ms 189376 KB Output is correct
9 Correct 105 ms 189256 KB Output is correct
10 Correct 121 ms 189512 KB Output is correct
11 Correct 113 ms 189768 KB Output is correct
12 Correct 106 ms 189512 KB Output is correct
13 Correct 106 ms 189512 KB Output is correct
14 Correct 106 ms 189540 KB Output is correct
15 Correct 111 ms 189516 KB Output is correct
16 Correct 114 ms 189512 KB Output is correct
17 Correct 107 ms 190292 KB Output is correct
18 Correct 116 ms 190536 KB Output is correct
19 Correct 113 ms 190516 KB Output is correct
20 Correct 112 ms 190652 KB Output is correct
21 Correct 113 ms 189556 KB Output is correct
22 Correct 114 ms 190592 KB Output is correct
23 Incorrect 115 ms 190476 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 189260 KB Output is correct
2 Correct 118 ms 189380 KB Output is correct
3 Correct 120 ms 189256 KB Output is correct
4 Correct 130 ms 189304 KB Output is correct
5 Correct 123 ms 189304 KB Output is correct
6 Correct 123 ms 189232 KB Output is correct
7 Correct 114 ms 189252 KB Output is correct
8 Correct 118 ms 189380 KB Output is correct
9 Correct 113 ms 189280 KB Output is correct
10 Correct 109 ms 189368 KB Output is correct
11 Correct 115 ms 189768 KB Output is correct
12 Correct 106 ms 189396 KB Output is correct
13 Correct 108 ms 189420 KB Output is correct
14 Correct 109 ms 189772 KB Output is correct
15 Correct 120 ms 189684 KB Output is correct
16 Correct 104 ms 189512 KB Output is correct
17 Correct 107 ms 190280 KB Output is correct
18 Correct 107 ms 190536 KB Output is correct
19 Correct 124 ms 190536 KB Output is correct
20 Correct 112 ms 190836 KB Output is correct
21 Correct 108 ms 189608 KB Output is correct
22 Correct 117 ms 190436 KB Output is correct
23 Incorrect 112 ms 190532 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 189256 KB Output is correct
2 Correct 115 ms 189188 KB Output is correct
3 Correct 115 ms 189264 KB Output is correct
4 Correct 111 ms 189256 KB Output is correct
5 Correct 113 ms 189256 KB Output is correct
6 Correct 130 ms 189272 KB Output is correct
7 Correct 114 ms 189256 KB Output is correct
8 Correct 117 ms 189260 KB Output is correct
9 Correct 114 ms 189252 KB Output is correct
10 Correct 110 ms 189508 KB Output is correct
11 Correct 111 ms 189768 KB Output is correct
12 Correct 113 ms 189512 KB Output is correct
13 Correct 116 ms 189512 KB Output is correct
14 Correct 113 ms 189768 KB Output is correct
15 Correct 113 ms 189512 KB Output is correct
16 Correct 118 ms 189568 KB Output is correct
17 Correct 117 ms 190132 KB Output is correct
18 Correct 119 ms 190536 KB Output is correct
19 Correct 115 ms 190500 KB Output is correct
20 Correct 120 ms 190756 KB Output is correct
21 Correct 117 ms 189512 KB Output is correct
22 Correct 119 ms 190556 KB Output is correct
23 Incorrect 110 ms 190708 KB Output isn't correct
24 Halted 0 ms 0 KB -