oj.uz

Submission #1110739

# Submission time Handle Problem Language Result Execution time Memory
1110739 2024-11-10T09:48:59 Z nhphuc Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 191 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define iii tuple<int, int, int>

const int N = 50500;
const int block = 200;

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

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; t = min(t, block + 1);
            if (dp[u][t] != -1)
                continue;
            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:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 240540 KB Output is correct
2 Correct 137 ms 240508 KB Output is correct
3 Correct 145 ms 240500 KB Output is correct
4 Correct 138 ms 240712 KB Output is correct
5 Correct 135 ms 240508 KB Output is correct
6 Correct 135 ms 240712 KB Output is correct
7 Correct 142 ms 240712 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 240612 KB Output is correct
2 Correct 141 ms 240468 KB Output is correct
3 Correct 148 ms 240500 KB Output is correct
4 Correct 146 ms 240664 KB Output is correct
5 Correct 159 ms 240492 KB Output is correct
6 Correct 148 ms 240712 KB Output is correct
7 Correct 145 ms 240712 KB Output is correct
8 Correct 147 ms 240712 KB Output is correct
9 Correct 146 ms 240712 KB Output is correct
10 Correct 134 ms 240632 KB Output is correct
11 Correct 138 ms 240968 KB Output is correct
12 Correct 146 ms 240620 KB Output is correct
13 Correct 150 ms 240740 KB Output is correct
14 Correct 147 ms 240768 KB Output is correct
15 Correct 151 ms 240968 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 240528 KB Output is correct
2 Correct 139 ms 240720 KB Output is correct
3 Correct 139 ms 240696 KB Output is correct
4 Correct 141 ms 240716 KB Output is correct
5 Correct 138 ms 240736 KB Output is correct
6 Correct 140 ms 240716 KB Output is correct
7 Correct 142 ms 240720 KB Output is correct
8 Correct 137 ms 240712 KB Output is correct
9 Correct 141 ms 240712 KB Output is correct
10 Correct 148 ms 240712 KB Output is correct
11 Correct 140 ms 240940 KB Output is correct
12 Correct 160 ms 240712 KB Output is correct
13 Correct 153 ms 240712 KB Output is correct
14 Correct 163 ms 240924 KB Output is correct
15 Correct 147 ms 240952 KB Output is correct
16 Correct 154 ms 240712 KB Output is correct
17 Correct 162 ms 240884 KB Output is correct
18 Correct 153 ms 240696 KB Output is correct
19 Correct 172 ms 240744 KB Output is correct
20 Correct 159 ms 240672 KB Output is correct
21 Correct 154 ms 240712 KB Output is correct
22 Correct 153 ms 240716 KB Output is correct
23 Correct 155 ms 240776 KB Output is correct
24 Correct 154 ms 240712 KB Output is correct
25 Correct 146 ms 240712 KB Output is correct
26 Correct 149 ms 240712 KB Output is correct
27 Correct 144 ms 240884 KB Output is correct
28 Correct 154 ms 241204 KB Output is correct
29 Correct 154 ms 241440 KB Output is correct
30 Correct 165 ms 240712 KB Output is correct
31 Correct 160 ms 241172 KB Output is correct
32 Correct 161 ms 240972 KB Output is correct
33 Correct 159 ms 241992 KB Output is correct
34 Correct 156 ms 241736 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 240712 KB Output is correct
2 Correct 172 ms 240696 KB Output is correct
3 Correct 154 ms 240712 KB Output is correct
4 Correct 147 ms 240716 KB Output is correct
5 Correct 150 ms 240724 KB Output is correct
6 Correct 150 ms 240700 KB Output is correct
7 Correct 148 ms 240488 KB Output is correct
8 Correct 146 ms 240720 KB Output is correct
9 Correct 146 ms 240712 KB Output is correct
10 Correct 135 ms 240756 KB Output is correct
11 Correct 141 ms 240868 KB Output is correct
12 Correct 140 ms 240712 KB Output is correct
13 Correct 141 ms 240720 KB Output is correct
14 Correct 144 ms 240968 KB Output is correct
15 Correct 154 ms 240968 KB Output is correct
16 Correct 131 ms 240716 KB Output is correct
17 Correct 133 ms 240908 KB Output is correct
18 Correct 136 ms 240644 KB Output is correct
19 Correct 142 ms 240716 KB Output is correct
20 Correct 140 ms 240644 KB Output is correct
21 Correct 139 ms 240712 KB Output is correct
22 Correct 160 ms 240712 KB Output is correct
23 Correct 154 ms 240712 KB Output is correct
24 Correct 159 ms 240712 KB Output is correct
25 Correct 155 ms 240716 KB Output is correct
26 Correct 156 ms 240712 KB Output is correct
27 Correct 159 ms 240712 KB Output is correct
28 Correct 161 ms 241324 KB Output is correct
29 Correct 157 ms 241216 KB Output is correct
30 Correct 154 ms 240712 KB Output is correct
31 Correct 159 ms 240972 KB Output is correct
32 Correct 163 ms 240968 KB Output is correct
33 Correct 148 ms 241992 KB Output is correct
34 Correct 147 ms 241976 KB Output is correct
35 Correct 172 ms 241872 KB Output is correct
36 Correct 169 ms 241068 KB Output is correct
37 Correct 176 ms 242560 KB Output is correct
38 Correct 177 ms 242372 KB Output is correct
39 Correct 173 ms 242232 KB Output is correct
40 Correct 191 ms 242204 KB Output is correct
41 Correct 170 ms 242228 KB Output is correct
42 Correct 154 ms 241480 KB Output is correct
43 Correct 160 ms 241680 KB Output is correct
44 Correct 168 ms 241584 KB Output is correct
45 Runtime error 185 ms 262144 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 240716 KB Output is correct
2 Correct 144 ms 240548 KB Output is correct
3 Correct 157 ms 240712 KB Output is correct
4 Correct 159 ms 240732 KB Output is correct
5 Correct 145 ms 240712 KB Output is correct
6 Correct 147 ms 240712 KB Output is correct
7 Correct 173 ms 240712 KB Output is correct
8 Correct 146 ms 240640 KB Output is correct
9 Correct 144 ms 240728 KB Output is correct
10 Correct 145 ms 240520 KB Output is correct
11 Correct 142 ms 240968 KB Output is correct
12 Correct 136 ms 240776 KB Output is correct
13 Correct 141 ms 240720 KB Output is correct
14 Correct 141 ms 240972 KB Output is correct
15 Correct 139 ms 240968 KB Output is correct
16 Correct 143 ms 240712 KB Output is correct
17 Correct 146 ms 241052 KB Output is correct
18 Correct 142 ms 240716 KB Output is correct
19 Correct 131 ms 240712 KB Output is correct
20 Correct 148 ms 240624 KB Output is correct
21 Correct 132 ms 240712 KB Output is correct
22 Correct 159 ms 240688 KB Output is correct
23 Correct 149 ms 240712 KB Output is correct
24 Correct 148 ms 240712 KB Output is correct
25 Correct 147 ms 240712 KB Output is correct
26 Correct 148 ms 240720 KB Output is correct
27 Correct 146 ms 240720 KB Output is correct
28 Correct 146 ms 241328 KB Output is correct
29 Correct 151 ms 241224 KB Output is correct
30 Correct 151 ms 241036 KB Output is correct
31 Correct 140 ms 240968 KB Output is correct
32 Correct 147 ms 240968 KB Output is correct
33 Correct 161 ms 241912 KB Output is correct
34 Correct 150 ms 241736 KB Output is correct
35 Correct 155 ms 241928 KB Output is correct
36 Correct 153 ms 240804 KB Output is correct
37 Correct 179 ms 242608 KB Output is correct
38 Correct 181 ms 242372 KB Output is correct
39 Correct 180 ms 242228 KB Output is correct
40 Correct 175 ms 242336 KB Output is correct
41 Correct 183 ms 242352 KB Output is correct
42 Correct 156 ms 241480 KB Output is correct
43 Correct 152 ms 241772 KB Output is correct
44 Correct 152 ms 241488 KB Output is correct
45 Runtime error 176 ms 262144 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -